题目概述

求多少序列 $\{A_n\},A_i\in[1,2^K)$ 满足 $B_1=A_1,B_i=B_{i-1}\ or\ A_i$ 的序列 $\{B_n\}$ 严格递增。

解题报告

不难转化成这样的模型：前 $i$ 个必须要比前 $i-1$ 个多出 $k(k>0)$ 个 $1$ ，求方案数。

那么这就是个背包问题，可以定义 $f_{i,j}$ 表示前 $i$ 个物品，已经出现了 $j$ 个有区别的 $1​$ 的方案数，则：

$$ f_{i,j}=\sum_{k=1}^{j}f_{i-1,j-k}2^{j-k}{K-j+k\choose k} $$

即枚举这次多出来的 $1$ 的个数 $k$ ，$2^{j-k}$ 表示之前已经存在的位数可以随便填 $0/1$ ，$K-j+k\choose k$ 表示从剩下的 $1$ 里面选出 $k$ 个作为这次多出来的 $1$ 。

我们会发现每次转移形式相同，所以想要用矩阵快速幂（显然不行）或者NTT来优化。

上面那个式子的形式不太好，不能凑成生成函数的形式，我们换下定义，令 $f_{i,j}$ 表示前 $i$ 个物品，已经出现了 $j$ 个无区别的 $1$ 的方案数，则：

$$ f_{i,j}=\sum_{k=1}^{j}f_{i-1,j-k}2^{j-k}{j\choose k} $$

这就变成指数型生成函数了，但是…… $f_{i-1,j-k}2^{j-k}$ 是什么鬼？这时候要使用套路QAQ，令 $\hat F_{i}(x)$ 为 $f_i$ 的指数型生成函数，则：

$$ \hat F_i(x)=\hat F_{i-1}(2x)*(e^x-1) $$

是的，这样就可以把 $2$ 弄到里面去了QAQ！由于 $\hat F_0(x)=1$ ，所以：

$$ \hat F_n(x)=\prod_{i=0}^{n-1}(e^{2^ix}-1) $$

再根据套路……这个东西可以左右拆分进行倍增，$\hat F_n(x)=\hat F_{n\over 2}(x)*\hat F_{n\over 2}(2^{n\over 2}x)$ 。

最后答案为 $\sum_{i=n}^{K}f_{n,i}{K\choose i}$ ，时间复杂度 $O(Klog_2nlog_2K)$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=30000,maxt=1<<16,MOD=998244353;

int n,K,t,fac[maxt+5],INV[maxt+5],f[maxt+5],g[maxt+5],ans,rev[maxt+5],pw[2][maxt+5];

inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
void Solve(int n){
    if (n==1) {for (int i=1;i<=K;i++) f[i]=INV[i];return;}Solve(n>>1);int pw=Pow(2,n>>1);
    for (int i=0;i<t;i++) g[i]=(LL)Pow(pw,i)*f[i]%MOD;NTT(f,t,1);NTT(g,t,1);
    for (int i=0;i<t;i++) f[i]=(LL)f[i]*g[i]%MOD;NTT(f,t,-1);for (int i=K+1;i<t;i++) f[i]=0;
    if (n&1){
        pw=Pow(2,n-1);g[0]=0;for (int i=1;i<=K;i++) g[i]=(LL)Pow(pw,i)*INV[i]%MOD;NTT(f,t,1);
        for (int i=K+1;i<t;i++) g[i]=0;NTT(g,t,1);for (int i=0;i<t;i++) f[i]=(LL)f[i]*g[i]%MOD;
        NTT(f,t,-1);for (int i=K+1;i<t;i++) f[i]=0;
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (t=1;t<=(K<<1);t<<=1);Make(t);Pre(t);Solve(n);
    for (int i=n;i<=K;i++) AMOD(ans,(LL)f[i]*fac[i]%MOD*C(K,i)%MOD);printf("%d\n",ans);return 0;
}