题解

首先根据容斥原理可以得到答案：

$$ \sum_{i\ge0}\left[\dfrac{z^i}{i!}\right]\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}z^j\right)^n $$

直接做是 $\mathcal{O}\left(n^2m^2\right)$ 的。

使用 NTT 可以优化到 $\mathcal{O}\left(n^2m\log n\right)$

由于计算答案时提取每一项的系数都一样，为 $i!$，即：

令 $\displaystyle G\left(z\right)=\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}z^j$，它的点值为 $\mathrm{d}=\operatorname{DFT}\left(G\right)$

假设 $G\left(z\right)^n$ 对应的点值为 $\mathrm{r}_n$，则 $\mathrm{r}_{n,i}=\mathrm{d}_{i}^n$

设 $\mathrm{v}=\left[\begin{matrix}1!\\2!\\\vdots\\\left(nm\right)!\end{matrix}\right]$

那么 $n$ 对应的答案为 $\mathrm{v}^\top\times \operatorname{IDFT}\times \mathrm{r}_{n}$

预处理出 $\mathrm{v}^\top\times \operatorname{IDFT}$，每次只要做一遍点积，复杂度降为 $\mathcal{O}\left(n^2m\right)$

由于 $n$ 对应的答案为 $\displaystyle\sum\left(\mathrm{v}^\top\times \operatorname{IDFT}\right)_i\cdot \mathrm{d}_{i}^n$，即需要求的为：对于每个 $n$，求出 $\displaystyle\sum_{i}b_ia_i^n$

这个可以分治 NTT 解决，复杂度降为 $\mathcal{O}\left(nm\log^2 nm\right)$

根据众所周知的定理：$t!=\int_{0}^\infty x^te^{-x}dx$，答案可以写为：

$$ \begin{aligned} F_{n}&=\int_{0}^\infty\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^ne^{-x}dx\\ &=-\int_{0}^\infty\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^n\left(-e^{-x}\right)dx\\ \end{aligned} $$

根据分部积分有：

$$ F_{n}=-\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^n\left(\int-e^{-x}\right)\left\vert\begin{matrix}\infty\\\\0\end{matrix}\right.+\int_{0}^\infty\left(\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^n\right)^{\prime}\left(\int-e^{-x}\right)dx $$

而根据 $\displaystyle \int-e^{-x}=e^{-x}$，且 $\displaystyle \forall k\gt 0,\lim_{x\to \infty} e^{-x}x^k=0$，$x=0$ 时 $\displaystyle \left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^n\left(\int-e^{-x}\right)=\left(-1\right)^{nm}$，因此

$$ \begin{aligned} F_n&=-\left(0-\left(-1\right)^{nm}\right)+\int_{0}^{\infty}n\cdot\left(\sum_{j\ge0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^{j-1}\cdot j\right)\cdot\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^{n-1}\cdot e^{-x}dx\\ &=\left(-1\right)^{nm}+n\sum_{j\ge 1}\dfrac{1}{\left(j-1\right)!}\binom{m}{j}\left(-1\right)^{m-j}\int_{0}^{\infty}x^{j-1}\cdot \left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^{n-1}\cdot e^{-x}dx\\ \end{aligned} $$

令 $\displaystyle F_{n,k}=\int_{0}^\infty\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^ne^{-x}\cdot x^{k}dx$

那么有递推式 $\displaystyle F_{n,k}=\left(-1\right)^{nm}\cdot\left[k=0\right]+k\cdot F_{n,k-1}+n\sum_{j\ge 1}\dfrac{1}{\left(j-1\right)!}\binom{m}{j}\left(-1\right)^{m-j}F_{n-1,k+j-1}$

而

$$ \begin{aligned} \displaystyle F_{n,m+k}&=\int_{0}^\infty\left(\sum_{j\ge 0}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}x^j\right)^ne^{-x}\cdot x^{m+k}dx\\&=m!\left(F_{n+1,k}-\sum_{0\le j\lt m}\dfrac{1}{j!}\binom{m}{j}\left(-1\right)^{m-j}F_{n,j+k}\right) \end{aligned} $$

因此可以把 $F_{n,m+1}$ 转化为 $F_{n+1,1},F_{n,1},F_{n,2},\dots F_{n,m}$ 的线性组合，于是对于每个 $n$，只需计算 $F_{n,0},F_{n,1},\cdots F_{n,m}$

复杂度 $\mathcal{O}\left(nm^2\right)$

根号分治一下即有 $\mathcal{O}\left(nm\sqrt{nm}\right)$ 的复杂度。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
constexpr int N=2010,p=998244353,G=3,AG=(p+1)/G;
int n,m,fac[N*N],ifac[N*N],inv[N*N],co[N];
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int binom(int a,int b){return 1ll*fac[a]*ifac[a-b]%p*ifac[b]%p;}
void redu(int &x,int y){x+=y;if(x>=p) x-=p;}
int redu(int x){return x>=p?x-p:x;}
namespace subtask1{
    int t1[N][N],t2[N][N],f[N*N];
    int solve(){
        int iv=fp(co[m],p-2);
        for(int i=0;i<m;++i) t1[0][i]=1ll*(i+1)*co[i+1]%p;t1[0][m]=0;
        for(int i=0;i<=m;++i) t2[0][i]=0;
        for(int i=1;i<=m;++i){
            for(int j=1;j<=m;++j) t1[i][j]=t1[i-1][j-1],t2[i][j]=t2[i-1][j-1];
            int num=1ll*t1[i-1][m]*iv%p;
            t2[i][1]=num;t1[i][0]=0;t2[i][0]=0;
            for(int j=1;j<=m;++j) redu(t1[i][j],p-1ll*num*co[j-1]%p);
        }
        for(int i=0;i<=m;++i){
            int cur=0;
            for(int j=0;j<=m;++j) cur=(cur+1ll*co[j]*fac[i+j])%p;
            f[i]=cur;
        }
        for(int i=2;i<=n;++i){
            for(int j=0;j<=m;++j){
                int pos=(i-1)*(m+1)+j,cc=((!j)?((i&m&1)?(p-1):1):0);
                int tot=0,bs=(i-2)*(m+1);
                for(int t=0;t<=m;++t) tot=(tot+1ll*f[bs+t]*t1[j][t])%p;
                bs=(i-1)*(m+1);
                for(int t=0;t<j;++t) tot=(tot+1ll*f[bs+t]*t2[j][t])%p;
                tot=1ll*i*tot%p;redu(tot,cc);
                if(j) tot=(tot+1ll*j*f[pos-1])%p;
                f[pos]=tot;
            }
        }
        int ans=0;
        for(int i=1;i<=n;++i) ans^=f[(i-1)*(m+1)];
        return ans;
    }
}
namespace subtask2{
    void ntt(int *pp,int b,int V){
        static ull tt[N*N];static int rev[N*N];rev[0]=0;
        for(int i=0;i<(1<<b);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(b-1)),tt[i]=pp[rev[i]];
        int bs=(V==1)?G:AG;int len=1<<b;
        for(int l=2;l<=len;l<<=1){
            int w=fp(bs,(p-1)/l);
            for(int mid=l>>1,j=0;j<len;j+=l){
                ull ww=1;
                for(int i=0;i<mid;++i,ww=ww*w%p){
                    ull t1=tt[i+j],t2=tt[i+j+mid]*ww%p;
                    tt[i+j]=t1+t2,tt[i+j+mid]=t1-t2+p;
                }
            }
        }
        if(V==-1){int k=fp(len,p-2);for(int i=0;i<len;++i) pp[i]=tt[i]%p*k%p;}
        else{for(int i=0;i<len;++i) pp[i]=tt[i]%p;}
    }
    int d[N*N],v[N*N],d1[N*N];
    int solve(){
        for(int i=0;i<=n*m;++i) v[i]=fac[i];
        for(int i=0;i<=m;++i) d[i]=co[i];
        int b=0;while((1<<b)<=n*m) ++b;
        ntt(d,b,1);ntt(v,b,-1);
        int ans=0;
        for(int j=0;j<(1<<b);++j) d1[j]=1ll*d[j]*v[j]%p;
        for(int i=1;i<=n;++i){
            int cur=0;
            for(int j=0;j<(1<<b);++j) redu(cur,d1[j]),d1[j]=1ll*d1[j]*d[j]%p;
            ans^=cur;
        }
        return ans;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    inv[1]=1;
    for(int i=2;i<N*N;++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    fac[0]=ifac[0]=1;
    for(int i=1;i<N*N;++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
    for(int i=0;i<=m;++i) co[i]=((m-i)&1)?(p-1ll*ifac[i]*binom(m,i)%p):(1ll*ifac[i]*binom(m,i)%p);
    if(m>600) printf("%d\n",subtask2::solve());
    else printf("%d\n",subtask1::solve());
    return 0;
}