题解

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define clr(name, n) memset(name, 0, (n + 1) * sizeof(name[0]))
#define mem(name, v, n) memset(name, v, (n + 1) * sizeof(name[0]))
#define ld cin
#define jyt cout
// #define int long long
constexpr int N = (1 << 20) + 7;
constexpr int P = 998244353;
namespace JoKing {
    struct poly {
        ll A, B;
        poly() {A = B = 0;}
        poly(ll X, ll Y) {A = X, B = Y;}
        inline poly lxl() {return poly(P - A, B);}
        friend poly operator + (poly X, poly Y) {return X.B == Y.B ? poly((X.A + Y.A + P) % P, X.B) : (X.B < Y.B ? X : Y);}
        friend poly operator - (poly X, poly Y) {return X.B == Y.B ? poly((X.A - Y.A + P) % P, X.B) : (X.B < Y.B ? X : Y.lxl());}
        friend poly operator * (poly X, poly Y) {return poly(X.A * Y.A % P, X.B + Y.B);}
    };
    inline long long qpow(long long x, long long y) {long long R = 1; for (; y; (x *= x) %= P, y >>= 1ll) if (y & 1ll) (R *= x) %= P; return R;}
    int n, m, a[N]; poly alpha[N], beta[N];
    inline void FWT(poly* a, ll op) {
        for (int len = 2, half = 1; len <= m; len <<= 1, half <<= 1)
            for (int l = 0; l < m; l += len)
                for (int k = 0; k < half; ++k)
                    a[l + half + k] = op ? a[l + half + k] + a[l + k] : a[l + half + k] - a[l + k];
    }
    signed main() { ll Ans = 0;
        ld >> n, m = (1 << n);
        REP(i, 0, m - 1) ld >> a[i];
        REP(i, 0, m - 1) alpha[i] = (a[i] == 998244352 ? poly(1, 1) : poly(a[i] + 1, 0));
        REP(i, 0, m - 1) {
            if (a[i] == 998244352) beta[i] = poly((a[i] * 2 + 1) % P, -2);
            else if (a[i] == 499122176) beta[i] = poly(qpow(a[i] + 1, P - 2) * qpow(a[i] + 1, P - 2) % P, 1);
            else beta[i] = poly(qpow(a[i] + 1, P - 2) * qpow(a[i] + 1, P - 2) % P * (a[i] * 2 + 1) % P, 0);
        }
        REP(j, 0, n - 1) PER(i, m - 1, 0) if (!(i & (1 << j))) alpha[i] = alpha[i] * alpha[i | (1 << j)];
        REP(j, 0, n - 1) PER(i, m - 1, 0)  if (!(i & (1 << j))) beta[i] = beta[i] * beta[i | (1 << j)];
        REP(i, 0, m - 1) (alpha[i].A *= qpow(P - 2, __builtin_popcount(i))) %= P, (beta[i].A *= qpow(qpow(2, __builtin_popcount(i)), P - 2)) %= P;
        FWT(alpha, 1); REP(i, 0, m - 1) alpha[i] = alpha[i] * alpha[i]; FWT(alpha, 0);
        REP(i, 0, m - 1) beta[i] = beta[i] * alpha[i], (Ans += !beta[i].B ? beta[i].A : 0ll) %= P;
        jyt << Ans << '\n';
        return 0;
    }
}
signed main() {
#ifdef WYY
    freopen("files/code.in", "r", stdin);
    freopen("files/code.out", "w", stdout);
    freopen("files/code.err", "w", stderr);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int Opt = 0, T = 0; ld >> Opt >> T;
    while (T--) JoKing::main();
    return 0;
}