求助神秘 RE

bamboo12345 @ 2025-01-10 19:51:33

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 21, maxn = (1 << N) + 5, mod = 998244353;
int n, m, p, x[maxn], y[maxn], w[maxn], val[maxn], inv[maxn], deg[maxn];
struct Poly {
    vector<int> a;
    void resize(int N) {
        a.resize(N);
    }
    int size() {
        return a.size();
    } 
    int& operator[](int x) {
        return a[x];
    }
    void FWT(int f) {
        for (int h = 2; h <= size(); h <<= 1) {
            for (int i = 0; i < size(); i += h) {
                for (int j = i; j < i + h / 2; j++) {
                    int a0 = a[j], a1 = a[j + h / 2];
                    a[j] = a0, a[j + h / 2] = (a1 + a0 * f + mod) % mod;
                }
            }
        }
    }
} ta[21 + 5], tb[21 + 5];
int pre[maxn];
int fnd(int x) {
    return (pre[x] == x ? x : pre[x] = fnd(pre[x]));
}
int qpow(int x, int k, int p) {
    int res = 1;
    while(k) {
        if(k & 1)
            res = res * x % p;
        x = x * x % p, k >>= 1;
    }
    return res;
}
int cnt[maxn];
signed main() {
    cin >> n >> m >> p;
    for (int i = 1; i <= m; i++) 
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 1; j <= n; j++)
            pre[j] = j;
        int val1 = 0, cnt = 0;
        for (int j = 1; j <= n; j++)
            val1 += ((i >> j - 1) & 1) * w[j], cnt += ((i >> j - 1) & 1), deg[j] = 0;
        for (int j = 1; j <= m; j++) {
            if(!((i >> x[j] - 1) & 1) || !((i >> y[j] - 1) & 1))
                continue;
            if(fnd(x[j]) != fnd(y[j]))
                pre[fnd(x[j])] = fnd(y[j]), cnt--;
            deg[x[j]]++, deg[y[j]]++;
        }
        bool flag = (cnt == 1);
        for (int j = 1; j <= n; j++)
            if(deg[j] % 2)
                flag = 0;
        if(!flag)
            val[i] = qpow(val1, p, mod);
        inv[i] = qpow(val1, p * (mod - 2), mod);
    }
    for (int i = 0; i <= n; i++)
        ta[i].resize(1 << n), tb[i].resize(1 << n);
    for (int i = 0; i < (1 << n); i++)
        cnt[i] = cnt[i >> 1] + (i & 1);
    for (int i = 0; i < (1 << n); i++)
        ta[cnt[i]][i] = val[i];
    for (int i = 0; i < (1 << n); i++)
        ta[i].FWT(1);
    tb[0][0] = 1;
    tb[0].FWT(1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++)
            for (int k = 0; k < (1 << n); k++)
                tb[i][k] = (tb[i][k] + ta[i - j][k] * tb[j][k]) % mod;
        tb[i].FWT(-1);
        for (int j = 0; j < (1 << n); j++)
            tb[i][j] = (cnt[j] == i ? tb[i][j] * inv[j] % mod : 0);
        tb[i].FWT(1);
    }
    cout << tb[n][(1 << n) - 1] << endl;
    return 0;
}

by TODAYS @ 2025-01-10 20:15:38

@bamboo12345

帮你开大了一点，就A了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 21, maxn = (1 << (N + 2)) + 5, mod = 998244353;
int n, m, p, x[maxn], y[maxn], w[maxn], val[maxn], inv[maxn], deg[maxn];
struct Poly {
    vector<int> a;
    void resize(int N) {
        a.resize(N);
    }
    int size() {
        return a.size();
    } 
    int& operator[](int x) {
        return a[x];
    }
    void FWT(int f) {
        for (int h = 2; h <= size(); h <<= 1) {
            for (int i = 0; i < size(); i += h) {
                for (int j = i; j < i + h / 2; j++) {
                    int a0 = a[j], a1 = a[j + h / 2];
                    a[j] = a0, a[j + h / 2] = (a1 + a0 * f + mod) % mod;
                }
            }
        }
    }
} ta[21 + 5], tb[21 + 5];
int pre[maxn];
int fnd(int x) {
    return (pre[x] == x ? x : pre[x] = fnd(pre[x]));
}
int qpow(int x, int k, int p) {
    int res = 1;
    while(k) {
        if(k & 1)
            res = res * x % p;
        x = x * x % p, k >>= 1;
    }
    return res;
}
int cnt[maxn];
signed main() {
    cin >> n >> m >> p;
    for (int i = 1; i <= m; i++) 
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 1; j <= n; j++)
            pre[j] = j;
        int val1 = 0, cnt = 0;
        for (int j = 1; j <= n; j++)
            val1 += ((i >> j - 1) & 1) * w[j], cnt += ((i >> j - 1) & 1), deg[j] = 0;
        for (int j = 1; j <= m; j++) {
            if(!((i >> x[j] - 1) & 1) || !((i >> y[j] - 1) & 1))
                continue;
            if(fnd(x[j]) != fnd(y[j]))
                pre[fnd(x[j])] = fnd(y[j]), cnt--;
            deg[x[j]]++, deg[y[j]]++;
        }
        bool flag = (cnt == 1);
        for (int j = 1; j <= n; j++)
            if(deg[j] % 2)
                flag = 0;
        if(!flag)
            val[i] = qpow(val1, p, mod);
        inv[i] = qpow(val1, p * (mod - 2), mod);
    }
    for (int i = 0; i <= n; i++)
        ta[i].resize(1 << n), tb[i].resize(1 << n);
    for (int i = 0; i < (1 << n); i++)
        cnt[i] = cnt[i >> 1] + (i & 1);
    for (int i = 0; i < (1 << n); i++)
        ta[cnt[i]][i] = val[i];
    for (int i = 0; i < (1 << n); i++)
        ta[i].FWT(1);
    tb[0][0] = 1;
    tb[0].FWT(1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++)
            for (int k = 0; k < (1 << n); k++)
                tb[i][k] = (tb[i][k] + ta[i - j][k] * tb[j][k]) % mod;
        tb[i].FWT(-1);
        for (int j = 0; j < (1 << n); j++)
            tb[i][j] = (cnt[j] == i ? tb[i][j] * inv[j] % mod : 0);
        tb[i].FWT(1);
    }
    cout << tb[n][(1 << n) - 1] << endl;
    return 0;
}

by bamboo12345 @ 2025-01-10 20:27:28

@TODAYS 过了，谢谢