萌新求助

EternalAlexander @ 2019-12-26 13:36:23

#include <bits/stdc++.h>
#define ll long long
const int mod=998244353;
int n,m,p,u[500],v[500],w[23],degr[23],sum[1<<22],f[23][1<<22],ok[1<<22],g[23][1<<22],inv[1<<22],size[1<<22];
namespace dsu {
    int fa[23];
    void reset(){std::memset(fa,0,sizeof(fa));}
    int getf(int x){return fa[x]?fa[x]=getf(fa[x]):x;}
    int merge(int x,int y){
        int f1=getf(x),f2=getf(y);
        if (f1==f2)return 0;
        fa[f2]=f1;return 1;
    }
}
inline int dec(int x){return x>=mod?x-mod:x;}

int qpow(int a,int b){
    if(b==0)return 1;
    int d=qpow(a,b>>1);d=(ll)d*d%mod;
    if (b&1)d=(ll)d*a%mod;
    return d;
}

int check(int S){
    int cnt=__builtin_popcount(S);
    dsu::reset();
    std::memset(degr,0,sizeof(degr));
    for(int i=1;i<=m;++i)
        if (((S>>(u[i]-1))&1)&&((S>>(v[i]-1))&1)){
            degr[u[i]]++;degr[v[i]]++;
            cnt-=dsu::merge(u[i],v[i]);
        }
    if (cnt>1)return 1;
    for(int i=1;i<=n;++i)if(degr[i]%2)return 1;
    return 0;
}

void fwt(int *a,int len,int flag){
    for(int i=1;i<len;i<<=1)
    for(int j=0;j<len;j+=i*2)
    for(register int k=0;k<i;++k){
        if(flag==1)a[j+k+i]=dec(a[j+k+i]+a[j+k]);
        else a[j+k+i]=dec(a[j+k+i]-a[j+k]+mod);
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&p);
    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){
        ok[S]=check(S);
        size[S]=__builtin_popcount(S);
        for(int i=1;i<=n;++i)if((S>>(i-1))&1){sum[S]=(sum[S]+w[i])%mod;}
        sum[S]=qpow(sum[S],p);
        g[size[S]][S]=ok[S]?sum[S]:0;
        inv[S]=qpow(sum[S],mod-2);
    }
    for(int i=0;i<=n;++i)fwt(g[i],1<<n,1);
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        fwt(f[i-1],1<<n,1);
        for(int j=0;j<i;++j)
        for(int k=0;k<(1<<n);++k)
            f[i][k]=dec(f[i][k]+(ll)f[j][k]*g[i-j][k]%mod);
        fwt(f[i],1<<n,-1);
        for(int j=0;j<(1<<n);++j)f[i][j]=size[j]==i?(ll)f[i][j]*inv[j]%mod:0;
    }
    printf("%d",f[n][(1<<n)-1]);
    return 0;
}

by zzy2333 @ 2019-12-26 13:51:32

by iotang @ 2019-12-26 14:18:02

金钩萌新

by disangan233 @ 2019-12-26 14:30:29

@EternalAlexander Orz EA /qq

by cmll02 @ 2020-02-02 15:17:58

吸氧

by 103PA @ 2020-05-25 20:58:02

卡常火车头不好嘛？

#include <bits/stdc++.h>
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define ll long long
const int mod=998244353;
int n,m,p,u[515],v[515],w[23],degr[23],sum[1<<22],f[23][1<<22],ok[1<<22],g[23][1<<22],inv[1<<22],size[1<<22];
namespace dsu {
    int fa[25];
    void reset(){std::memset(fa,0,sizeof(fa));}
    int getf(int x){return fa[x]?fa[x]=getf(fa[x]):x;}
    int merge(int x,int y){
        int f1=getf(x),f2=getf(y);
        if (f1==f2)return 0;
        fa[f2]=f1;return 1;
    }
}
inline int dec(int x){return x>=mod?x-mod:x;}

int qpow(int a,int b)
{
    if(b==0)
        return 1;
    int d=qpow(a,b>>1);d=(ll)d*d%mod;
    if (b&1)d=(ll)d*a%mod;
    return d;
}

int check(int S){
    int cnt=__builtin_popcount(S);
    dsu::reset();
    std::memset(degr,0,sizeof(degr));
    for(int i=1;i<=m;++i)
        if (((S>>(u[i]-1))&1)&&((S>>(v[i]-1))&1)){
            degr[u[i]]++;degr[v[i]]++;
            cnt-=dsu::merge(u[i],v[i]);
        }
    if (cnt>1)return 1;
    for(int i=1;i<=n;++i)if(degr[i]%2)
    {
        return 1;
    }
    return 0;
}

void fwt(int *a,int len,int flag)
{
    for(int i=1;i<len;i<<=1)
    for(int j=0;j<len;j+=i*2)
    for(register int k=0;k<i;++k){
        if(flag==1)a[j+k+i]=dec(a[j+k+i]+a[j+k]);
        else a[j+k+i]=dec(a[j+k+i]-a[j+k]+mod);
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&p);
    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){
        ok[S]=check(S);
        size[S]=__builtin_popcount(S);
        for(int i=1;i<=n;++i)if((S>>(i-1))&1){sum[S]=(sum[S]+w[i])%mod;}
        sum[S]=qpow(sum[S],p);
        g[size[S]][S]=ok[S]?sum[S]:0;
        inv[S]=qpow(sum[S],mod-2);
    }
    for(int i=0;i<=n;++i)fwt(g[i],1<<n,1);
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        fwt(f[i-1],1<<n,1);
        for(int j=0;j<i;++j)
        for(int k=0;k<(1<<n);++k)
            f[i][k]=dec(f[i][k]+(ll)f[j][k]*g[i-j][k]%mod);
        fwt(f[i],1<<n,-1);
        for(int j=0;j<(1<<n);++j)f[i][j]=size[j]==i?(ll)f[i][j]*inv[j]%mod:0;
    }
    printf("%d",f[n][(1<<n)-1]);
    return 0;
}