自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 22:33:35，当前版本为作者最后更新于2021-08-25 10:46:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

方便起见，下文用 $n$ 表示原题中的 $2^n$。

我们注意到 $\text{DFT}$ 这个东西实际上就是乘一个范德蒙德矩阵：

$$V= \begin{bmatrix} 1&1&1&\cdots&1\\ 1&\omega&\omega^2&\cdots&\omega^{n-1}\\ 1&\omega^2&\omega^4&\cdots&\omega^{2(n-1)}\\ 1&\omega^3&\omega^6&\cdots&\omega^{3(n-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega^{n-1}&\omega^{2(n-1)}&\cdots&\omega^{(n-1)(n-1)}\\ \end{bmatrix} $$

因此计算 $\text{DFT}^k$ 实际也就是计算这个矩阵的 $k$ 次方。

我们先手算一下 $V^2$ 试试：

$$V^2_{ij}=\sum_{k=0}^{n-1}\omega^{ik+kj}=\left(\sum_{k=0}^{n-1}\omega^{k}\right)\omega^{i+j} $$

注意到除非 $i+j=n$ 或 $i+j=0$，那么这个 $\sum\omega^k$ 就会直接变成 $0$ 把整个消掉。

也就是说，$V$ 平方之后大概是个这个样子：

$$V^2= \begin{bmatrix} n&0&0&\cdots&0\\ 0&0&0&\cdots&n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&n&\cdots&0\\ 0&n&0&\cdots&0\\ \end{bmatrix} $$

我们惊讶地发现把一个东西乘上 $V^2$ 实际上就等价于：

每一项都乘上 $n$，然后翻转后 $n-1$ 项。

也就是说，如果再乘上 $V^4$，后 $n-1$ 项转了回来，那就相当于每一项乘上 $n^2$。

那么我们先算出来 $\left\lfloor\dfrac{k}{4}\right\rfloor$ 先乘一下，再做 $k\bmod 4$ 次 NTT 就行了。

时间复杂度为 $O(n\log n+n\log k)$。

#include<complex>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>

#define int long long
#define MAXN 2100000

using namespace std;

int x[MAXN],y[MAXN],z[MAXN];
int N,M;

int read(){
	int x=0;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar());
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x;
}

int rev[MAXN],k,L;

const int mod=998244353;
const int g=3;
const int g1=332748118;

void init(){
    rev[0]=0;
    for(int i=0;i<k;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
}

int ksm(int x,int y){
    x%=mod;int ans=1;
    for(int i=y;i;i>>=1,x=x*x%mod)if(i&1)ans=ans*x%mod;
    return ans%mod;
}

void ntt(int *a,int sz,int tag){
    for(int i=1;i<sz;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    int n=log2(sz);
    for(int i=1;i<=n;i++){
        int m=1<<i,wn;
        if(tag==1)wn=ksm(g,(mod-1)/(m));
        else wn=ksm(g1,(mod-1)/(m));
        for(int j=0;j<sz;j+=m){
            int omega=1;
            for(int l=0;l<m/2;l++){
                int x=omega*a[j+l+m/2]%mod,y=a[j+l]%mod;
                a[j+l]=(y+x)%mod;a[j+l+m/2]=(y-x+mod)%mod;
                omega=omega*wn%mod;
            }
        }
    }
}

int K,qwq;

signed main(){

    qwq=read(),K=read();
    N=(1<<qwq)-1;
    for(int i=0;i<=N;i++)x[i]=(read()+mod)%mod;

    for(k=1,L=0;k<=N;k<<=1,L++);

    int qwq=(int)(K/4)*2;K%=4;
    for(int i=0;i<=N;i++)x[i]=x[i]*(ksm((N+1),qwq)%mod)%mod;

    init();
    for(int i=1;i<=K;i++)ntt(x,k,1);

    for(int i=0;i<=N;i++)cout<<x[i]%mod<<" ";
    puts("");

    return 0;
}