C++(g++ 7.5.0) 解法, 执行用时: 3970ms, 内存消耗: 26976K, 提交时间: 2022-08-17 09:54:57

#include<bits/stdc++.h>
const int N = (1 << 20) | 1;
using namespace std;
#define int long long
int n, m, t, p, b[N], a[N], mod, e[N];
void XOR(int *f, int type) {
    for(int mid = 1; mid < n; mid <<= 1)
        for(int len = mid << 1, j = 0; j < n; j += len)
            for(int k = 0; k < mid; k ++) {
                int x = f[j + k] % mod, y = f[j + k + mid] % mod;
                f[j + k] = (x + y) % mod;
                f[j + k + mid] = (x - y + mod) % mod;
            }
    if(type == -1) {
        for(int i = 0; i < n; i ++) f[i] = f[i] / n;
    }
}
int mul(int a, int b, int mod) {
    return (a * b - (int)((long double)a / mod * b) * mod + mod) % mod ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> t >> p;
    n = 1 << m; mod = p * n;
    for(int i = 0; i < n; i ++) cin >> e[i];
    for(int i = 0; i <= m; i ++)
        cin >> b[i];
    for(int i = 0; i < n; i ++)
        a[i] = b[__builtin_popcount(i)];
    XOR(e, 1); XOR(a, 1);
    while(t) {
        if(t & 1) {
            for(int i = 0; i < n; i ++)
                e[i] = mul(e[i], a[i], mod); 
        }
        t >>= 1;
        for(int i = 0; i < n; i ++)
            a[i] = mul(a[i], a[i], mod);
    }
    XOR(e, -1);
    for(int i = 0; i < n; i ++)
        cout << e[i] << "\n";
}

C++ 解法, 执行用时: 4561ms, 内存消耗: 35152K, 提交时间: 2022-03-04 20:24:10

 #include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int> 
using namespace std;
template<class T>
inline void read(T &x){
    x=0; int sign=1; char c;
    do{ c=getchar(); if(c=='-') sign=-1; }while(!isdigit(c));
    do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
    x*=sign;
}
const int N=2e6+50;
ll mod;
inline ll qpow(ll a,ll b){
	ll ans=1LL;
	for(;b;b>>=1,a=(__int128)a*a%mod) if(b&1) ans=(__int128)ans*a%mod;
	return ans;
}
int n,m;
void FWT(ll *a,int sign){
	for(int k=n,len=1<<(n-1);k>=1;--k,len>>=1)
	for(int i=0;i<m;i+=1<<k)
	for(int j=i;j<i+len;++j)
	a[j]=(a[j]+a[j+len])%mod,
	a[j+len]=(a[j]+mod-a[j+len]+mod-a[j+len])%mod;
}
ll t,a[N],b[N],c[N];
int main(){
	read(n),read(t),read(mod);
	m=1<<n,mod*=m;
	for(int i=0;i<m;++i) read(a[i]),a[i]%=mod;
	for(int i=0;i<=n;++i) read(c[i]),c[i]%=mod;
	for(int i=1;i<m;++i) b[i]=b[i>>1]+(i&1);
	for(int i=0;i<m;++i) b[i]=c[b[i]];
	FWT(a,1),FWT(b,1);
	for(int i=0;i<m;++i) c[i]=(__int128)qpow(b[i],t)*a[i]%mod;
	FWT(c,1);
	for(int i=0;i<m;++i) printf("%lld\n",c[i]/m);
	return 0;
}