HN省队集训D1T3 Or
生地会考后发现自己连NTT的板子都不会打了....
果然是好久没写代码了...
准备重新学习FFT和NTT和FWT
题意
给定\(n,k\)，问有多少个长度为n的序列A使得每个元素在\([1,2^k)\)中且A的or前缀和序列B是递增序列。
46分\(n,k\le 300\)
59分\(n\le 700,k\le 2000\)
100分\(n,k\le 3\cdot10^4\)
注意：以下“位数”指的是为1的二进制位数。
46分
由于\(B_i=A_i\ or\ B_{i-1}\)，显然B是非严格递增的。
我们只需要每个\(A_i\)至少有一个二进制位为1而\(B_{i-1}\)那一位为0。
设\(f_i(j)\)为长度为i，\(B_i\)位数为j有多少种方案。 \[ f_i(j)=\sum_{t=0}^{j-1}f_{i-1}(t)2^t\binom{k-t}{j-t} \]
怎么得到的呢？
枚举\(B_{i-1}\)的位数t，然后\(f_{i-1}(t)\)就代表先确定\(B_{i-1}\)这t位是1，在此基础上，\(A_{i}\)这t位可以为0或1（\(2^t\)种方案）
然后再在这k-t位里面选出j-t位，使得\(A_i\)这j-t位是1，另外\(n-j\)位是0。
\(O(nk^2)\)
（非常显然是吧）
59分
拆组合数得到 \[ f_i(j)=\sum_{t=0}^{j-1}f_{i-1}(t)2^t\frac{(k-t)!}{(j-t)!(k-j)!}\\ (k-j)!f_i(j)=\sum_{t=0}^{j-1}f_{i-1}(t)2^t\frac{(k-t)!}{(j-t)!} \] 由于k是常数，我们设\(dp_i(j)=(k-j)!f_i(j)\)，则柿子可以化成： \[ dp_i(j)=\sum_{t=0}^{j-1}dp_{i-1}(t)2^t\frac{1}{(j-t)!} \] 很显然这就是一个卷积的形式了。
记\(F_j=dp_i(j),G_j=dp_{i-1}(j)2^j,H_j=\frac{1}{j!}\)
显然\(H_0=0\)
那么\(F=G\ast H\)
\(O(nk\log k)\)
100分
考虑生成函数，设\(A_i(x)=\sum_{j=0}^\infty dp_i(j)x^j\)，\(B(x)=\sum_{i=1}^\infty \frac{1}{i!}x^i=(e^x-1)\)
所以 \[ A_n(x)=A_{n-1}(2x)B(x)=A_0(x^n)\prod_{i=0}^{n-1} B(2^ix)=k!\prod_{i=0}^{n-1}(e^{2^ix}-1) \] 设\(A_n(x)=\prod_{i=0}^{n-1}(e^{2^ix}-1)\)
考虑分治计算：
如果\(n\)为奇数，则\(A_n(x)=A_{n-1}(x)(e^{2^{n-1}}-1)\)
否则\(A_n(x)=A_{\frac{n}{2}}(x)A_\frac{n}{2}(2^{\frac{n}{2}}x)\)
计算的时候，需要\(\bmod x^{k+1}\)，只能通过拿两个k次多项式卷积以后，把后面的项删去就又只有k次了
时间复杂度\(O(k\log n\log k)\)
/*
Author: CNYALI_LK
LANG: C++
PROG: or.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
const ll p=998244353;
ll fac[102423],inv[102423],invf[102423],p2[102423];
ll C(ll n,ll k){
return fac[n]*invf[k]%p*invf[n-k]%p;
}
ll fpm(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=a*c%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll n,m,f[102423],g[102423],rev[102423],s,t,omega[102423],reo[102423];
void FFT(ll *f,ll flag){
for(ll i=0;i<s;++i)if(i<rev[i])swap(f[i],f[rev[i]]);
for(ll i=1;i<s;i<<=1){
ll w=flag>0?omega[i]:reo[i];
for(ll j=0;j<s;j+=i+i){
ll aw=1,xa,xb;
for(ll k=0;k<i;++k){
xa=f[j+k],xb=aw*f[j+k+i]%p;
f[j+k]=(xa+xb)%p;
f[j+k+i]=(xa-xb+p)%p;
aw=aw*w%p;
}
}
}
if(flag<0){
for(ll i=0;i<s;++i)f[i]=f[i]*inv[s]%p;
}
}
void calc(ll n){
if(n==1){
for(ll i=1;i<=m;++i)f[i]=invf[i];
return;
}
if(n&1){
calc(n-1);
for(ll i=0;i<s;++i)g[i]=0;
ll pow2=1;
for(ll i=1;i<=m;++i){pow2=pow2*p2[n-1]%p;g[i]=invf[i]*pow2%p;}
FFT(f,1);
FFT(g,1);
for(ll i=0;i<s;++i)f[i]=f[i]*g[i]%p;
FFT(f,-1);
f[0]=0;
for(ll i=m+1;i<s;++i)f[i]=0;
}
else{
calc(n>>1);
for(ll i=0;i<s;++i)g[i]=0;
ll pow2=1;
for(ll i=1;i<=m;++i){pow2=pow2*p2[n>>1]%p;g[i]=pow2%p*f[i]%p;}
FFT(f,1);
FFT(g,1);
for(ll i=0;i<s;++i){
f[i]=f[i]*g[i]%p;
}
FFT(f,-1);
for(ll i=m+1;i<s;++i)f[i]=0;
}
}
int main(){
freopen("or.in","r",stdin);
freopen("or.out","w",stdout);
n=read();m=read();
for(s=1;s<=m;s<<=1,++t);
s<<=1;
omega[s>>1]=fpm(3,998244352/s);
reo[s>>1]=fpm(omega[s>>1],998244351);
for(ll i=s>>2;i;i>>=1){
omega[i]=omega[i<<1]*omega[i<<1]%p;
reo[i]=reo[i<<1]*reo[i<<1]%p;
}
for(ll i=1;i<s;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<t);
fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
p2[0]=1;p2[1]=2;
for(ll i=2;i<=s;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=invf[i-1]*inv[i]%p;
p2[i]=(p2[i-1]<<1)%p;
}
calc(n);
ll ans=0;
for(ll i=1;i<=m;++i)ans=(ans+f[i]*invf[m-i]%p*fac[m])%p;
printf("%lld\n",ans);
return 0;
}