C++ 解法, 执行用时: 3179ms, 内存消耗: 185072K, 提交时间: 2023-08-12 10:17:25

#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); i++)
#define ROF(i, r, l) for(int i = (r); i >= (l); i--)
#define sz(a) int((a).size())
#define vi vector<int>
#define ll long long
#define LL __int128
#define ull unsigned long long
using namespace std;
const int N = 20,P=998244353;
const ll lim = (ull)P * P * 15;
int n;
int a[1 << N], b[1 << N], c[1 << N];
int f[N+1][1<<N],g[N+1][1<<N];
int ans[N+1];
int dp1[N+1],dp2[N+1];
ull tmp[N+1];
int power(int a, int b, int c = 1) {
    for(; b; b >>= 1, a = (ll)a * a % P) if(b & 1) c = (ll)c * a % P;
    return c;
}
void FWT(int a[], int t) {
    t = (t + P) % P;
    for(int i = 2; i <= (1 << n); i <<= 1) {
        for(int j = 0; j < (1 << n); j += i) {
            for(int k = 0; k < (i>>1);k++) {
                (a[j+k+(i>>1)]+=(ll)a[j+k]*t%P)%=P;
            }
        }
    }

}
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    int full=(1<<n)-1;
    FOR(i, 1, (1 << n) - 1) cin >> a[i];
    FOR(i, 1, (1 << n) - 1) cin >> b[i];
    FOR(i, 1, (1 << n) - 1) c[i] = c[i >> 1] + (i & 1);
    FOR(i,1,(1<<n)-1){
        g[c[i]][i]=a[i];
        int ri=i^full;
        f[c[ri]][ri]=b[i];
    }
    FOR(i,0,n)FWT(f[i],1),FWT(g[i],1);
    FOR(i,0,(1<<n)-1){
        FOR(j,0,n)dp1[j]=f[j][i],dp2[j]=g[j][i];
        FOR(j,0,n-1){
            FOR(k,0,n)tmp[k]=0;
            ROF(k,n,j){
                FOR(l,1,n-k){
                    tmp[k+l]+=(ll)dp1[k]*dp2[l];
                    if(tmp[k+l]>=lim)tmp[k+l]%=P;
                }
            }
            FOR(k,0,n)dp1[k]=tmp[k]%P;
            int op = c[full ^ i] & 1;
            if(op) (ans[j+1]+=P-dp1[n])%=P;
            else (ans[j+1]+=dp1[n])%=P;
        }
    }
    int ifac=1;
    FOR(i,1,n){
        ifac=(ll)ifac*power(i,P-2)%P;
        cout<<(ll)ans[i]*ifac%P<<" ";
    }
    cout << "\n";
}