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$
题解（感谢你群最强之一dkw聚聚的帮助）
注意：以下“位数”指的是为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;
}