You are given positive integers $N$ and $K$. Find the number, modulo $998244353$, of integer sequences $\bigl(f(0), f(1), \ldots, f(2^N-1)\bigr)$ that satisfy all of the following conditions: Here, $\mathrm{AND}$ and $\mathrm{OR}$ denote the bitwise AND and OR, respectively.Problem Statement
Constraints
Input
Input is given from Standard Input in the following format:
$N$ $K$
Output
Print the number, modulo $998244353$, of integer sequences that satisfy the conditions.
Sample Input 1
2 1
Sample Output 1
6
The following six integer sequences satisfy the conditions:
- $(0,0,0,0)$
- $(0,1,0,1)$
- $(0,0,1,1)$
- $(1,0,1,0)$
- $(1,1,0,0)$
- $(1,1,1,1)$
Sample Input 2
2 2
Sample Output 2
19
Sample Input 3
100 123456789123456789
二进制的题，考虑拆位处理。
那么会发现，当我们确定了 \(f(0),f(1)\cdots f(2^n)\) 时，整个函数就确定了
具体写出来，就是 \(f(2^{p_1}+2^{p_2}+\cdots+2^{p_m})=(\sum\limits_{i=1}^mf(2^{p_i})-f(0))+f(0)\)
这个式子可以直接打表推出来
那么此时我们知道了所有 \(f(2^p_i)-f(0)\) 的值，我们能否知道有多少个合法的 \(f(0)\)？
注意有 \(f(x)\) 的限制，所以要满足任意的数，\(0\le (\sum\limits_{i=1}^m(f(2^{p_i})-f(0)))+f(0)\le K\)
上面这个式子的最大值和最小值一定是所有正数的和(设为 \(s1\))和所有负数的和(设为s2)，那么
\[s2+f(0)\ge 0,s1+f(0)\le k,-s2\le f(0)\le K-s1 \]共有 \(K-s1+s2+1\) 种选法
注意到 \(s1-s2=\sum\limits_{i=0}^n|f(2^i)|\)
我们可以往这个方向去列式子。枚举最后的绝对值之和。
\[\sum\limits_{i=n}^{K+1}(K-i+1)C_{i-1}^{n-1} \]\[=(K+1)\sum\limits_{i=n}^{K+1}C_{i-1}^{n-1}-\sum\limits_{i=n}^{K+1}iC_{i-1}^{n-1} \]\[=(K+1)\sum\limits_{i=n}^{K+1}C_{i-1}^{n-1}-n\sum\limits_{i=n}^{K+1}C_i^n(融入公式) \]\[=(K+1)C_{K+1}^n-nC_{K+2}^{n+1}(上指标求和) \]\[=C_{K+1}^{n+1}(通分可得，不写了) \]此时我们还要给每个数分配正负，发现0我们无法分配。枚举有多少个非0点，然后给答案加上 \(C_{K+1}^{i+1}\times 2^i\times C_n^i\)
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,P=998244353;
int n,f[N],iv[N],inv[N],c[N],ans;
long long k;
int C(int x,int y)
{
return 1LL*f[x]*iv[y]%P*iv[x-y]%P;
}
int main()
{
scanf("%d%lld",&n,&k);
c[f[0]=f[1]=iv[0]=iv[1]=inv[1]=c[0]=1]=(k+1)%P;
for(int i=2;i<N;i++)
{
f[i]=1LL*f[i-1]*i%P;
inv[i]=(P-P/i)*1LL*inv[P%i]%P;
iv[i]=1LL*iv[i-1]*inv[i]%P;
c[i]=c[i-1]*((k-i+2)%P)%P*inv[i]%P;
}
for(int i=0,pw=1;i<=n;i++,(pw<<=1)%=P)
(ans+=1LL*pw*C(n,i)%P*c[i+1]%P)%=P;
// printf("%d %d %d\n",i,pw,c[i+1]);
printf("%d",ans);
}