IOI2021 @ 2019-09-30 08:18:44

by IOI2021 @ 2019-09-30 08:18:56

RT

by IOI2021 @ 2019-09-30 08:19:56

这题不卡常T了四次 97'

#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
void fwt(ll *a, int len, int opt){
    for(int i = 2; i <= len; i <<= 1)
        for(int p = i >> 1, j = 0; j + i <= len; j += i)
            for(int k = j; k < j + p; k ++)
                a[p + k] =(a[p + k] + opt * a[k] + mod) % mod;
}
ll qpow(ll x, int y){
    ll ret = 1;
    for(;y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
int fa[25];
int get(int x){
    return fa[x] == x? x:(fa[x] = get(fa[x]));
}
void merge(int x , int y){
    x = get(x), y = get(y);
    fa[x] = y;
}
int n, m, q, a[25][25], w[25], he[1 << 23], ok[1 << 23], du[25], U[1000005], V[1000005], bitcount[1 << 23];
ll f[23][(1 << 22)], g[23][1 << 22];
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; i ++) scanf("%d%d", &U[i], &V[i]);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for(int S = 0; S < (1 << n); S ++){

        int bb = 0;
        for(int i = 1; i <= n; i ++){
            if((1 << (i - 1)) & S) he[S] += w[i], bb ++;
            du[i] = 0, fa[i] = i;
        }
        bitcount[S] = bb;

        for(int i = 1; i <= m; i ++){
            if(((1 << (U[i] - 1)) & S) && ((1 << (V[i] - 1)) & S)){
                if(get(U[i]) != get(V[i])) merge(U[i], V[i]), bb --;
                du[U[i]] ++;
                du[V[i]] ++;
            }
        }

        if(bb != 1) ok[S] = 1;
        int cnt = 0;
        for(int i = 1; i <= n; i ++) 
            cnt += (du[i] & 1);
        if(cnt) ok[S] = 1;

        if(ok[S]) g[bitcount[S]][S] = qpow(he[S], q);
    }
    for(int i = 0; i <= n; i ++) fwt(g[i], 1 << n, 1);
    f[0][0] = 1; fwt(f[0], 1 << n, 1);
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= i - 1; j ++)
            for(int k = 0; k < (1 << n); k ++)
                f[i][k] += f[j][k] * g[i - j][k] % mod, f[i][k] %= mod;
        fwt(f[i], 1 << n, -1);

        for(int j = 0; j < (1 << n); j ++) f[i][j] = bitcount[j] == i? f[i][j] * qpow(qpow(he[j], mod - 2), q) % mod:0;
        if(i != n) fwt(f[i], 1 << n, 1);
    }
    printf("%lld", f[n][(1 << n) - 1]);
    return 0;
}

by IOI2021 @ 2019-09-30 08:20:35

后来吸了臭氧才卡过去

求助如何优化QWQ(不卡常)

by k1saki @ 2019-09-30 08:22:36

qndmx

by lygmh @ 2019-09-30 08:22:55

qndmx

by Provicy @ 2019-09-30 08:26:52

QNDMX

by IOI2021 @ 2019-09-30 08:28:44

突然发现没有预处理inv导致多了一个log

但为什么还是T \快哭了

#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
void fwt(ll *a, int len, int opt){
    for(int i = 2; i <= len; i <<= 1)
        for(int p = i >> 1, j = 0; j + i <= len; j += i)
            for(int k = j; k < j + p; k ++)
                a[p + k] =(a[p + k] + opt * a[k] + mod) % mod;
}
ll qpow(ll x, int y){
    ll ret = 1;
    for(;y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
int fa[25];
int get(int x){
    return fa[x] == x? x:(fa[x] = get(fa[x]));
}
void merge(int x , int y){
    x = get(x), y = get(y);
    fa[x] = y;
}
int n, m, q, a[25][25], w[25], he[1 << 23], ok[1 << 23], du[25], U[1000005], V[1000005], bitcount[1 << 23];
ll f[23][1 << 22], g[23][1 << 22], inv[1 << 22];
int main(){
    scanf("%d%d%d", &n, &m, &q);
    int len = 1 << n;
    for(int i = 1; i <= m; i ++) scanf("%d%d", &U[i], &V[i]);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for(int S = 0; S < len; S ++){

        int bb = 0;
        for(int i = 1; i <= n; i ++){
            if((1 << (i - 1)) & S) he[S] += w[i], bb ++;
            du[i] = 0, fa[i] = i;
        }
        bitcount[S] = bb;

        for(int i = 1; i <= m; i ++){
            if(((1 << (U[i] - 1)) & S) && ((1 << (V[i] - 1)) & S)){
                if(get(U[i]) != get(V[i])) merge(U[i], V[i]), bb --;
                du[U[i]] ++;
                du[V[i]] ++;
            }
        }

        if(bb != 1) ok[S] = 1;
        int cnt = 0;
        for(int i = 1; i <= n; i ++) 
            cnt += (du[i] & 1);
        if(cnt) ok[S] = 1;

        if(ok[S]) g[bitcount[S]][S] = qpow(he[S], q);
        inv[S] = qpow(qpow(he[S], mod - 2), q);
    }
    for(int i = 0; i <= n; i ++) fwt(g[i], 1 << n, 1);
    f[0][0] = 1; fwt(f[0], 1 << n, 1);
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= i - 1; j ++)
            for(int k = 0; k < len; k ++)
                f[i][k] += f[j][k] * g[i - j][k] % mod, f[i][k] %= mod;
        fwt(f[i], 1 << n, -1);

        for(int j = 0; j < len; j ++) f[i][j] = bitcount[j] == i? f[i][j] * inv[j] % mod:0;
        if(i != n) fwt(f[i], 1 << n, 1);
    }
    printf("%lld", f[n][len - 1]);
    return 0;
}

by IOI2021 @ 2019-09-30 08:29:17

也不是多了log，就是常数大了

但还是T QWQ

by 谢谢_对不起 @ 2019-09-30 08:34:59

qndmx

by JBLee @ 2019-09-30 08:56:57

萌新就切黑题%%%