萌新求助CE

275307894a @ 2021-09-18 20:19:33

by 275307894a @ 2021-09-18 20:19:46

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 21
#define K (1<<N)
#define mod 998244353
#define Mod 998244352
#define eps (1e-4)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
using namespace std;
int n,m,k,p,x[N*N+5],y[N*N+5],In[N+5],W[K+5],H[K+5],cnt,un,wn,Fl,lg[K+5],fa[K+5],F1[N+1][K+5],F2[N+1][K+5];ll G[K+5],Inv[K+5];
I ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
I void OR(int *A,int n,int Fl){
    RI i,j,h;for(i=2;i<=n;i<<=1){
        for(j=0;j<n;j+=i) for(h=j;h<j+i/2;h++) A[h+i/2]=(1ll*A[h+i/2]+mod+A[h]*Fl)%mod;
    }
}I int Getfa(int x){return x==fa[x]?x:fa[x]=Getfa(fa[x]);}
I void merge(int x,int y){un=Getfa(x);wn=Getfa(y);un^wn&&(fa[un]=wn,cnt--);}
int main(){
    freopen("1.in","r",stdin);
    RI i,j,h;scanf("%d%d%d",&n,&m,&p);k=1<<n;for(i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);for(i=1;i<=n;i++)scanf("%d",&W[i]);for(i=1;i<k;i++) lg[i]=lg[i/2]+1;
    for(i=1;i<k;i++)H[i]=H[i>>1]+(i&1),G[i]=(G[i^(i&-i)]+W[lg[i&-i]])%mod;
    for(i=0;i<k;i++){
        Me(In,0);for(j=1;j<=n;j++) fa[j]=j;cnt=H[i];G[i]=mpow(G[i],p);Inv[i]=G[i]?mpow(G[i]):1;for(j=1;j<=m;j++) i>>(x[j]-1)&1&&i>>(y[j]-1)&1&&(merge(x[j],y[j]),In[x[j]]^=1,In[y[j]]^=1);
        for(Fl=j=1;j<=n;j++) i>>(j-1)&1&&(Fl&=In[j]^1);F1[H[i]][i]=G[i]*(Fl^1||cnt^1);
    }F2[0][0]=1;OR(F2[0],k,1);for(i=1;i<=n;i++){
        OR(F1[i],k,1);for(j=1;j<=i;j++) for(h=0;h<k;h++) F2[i][h]=(F2[i][h]+1ll*F1[j][h]*F2[i-j][h])%mod;OR(F2[i],k,-1);
        for(j=0;j<k;j++) F2[i][j]=1ll*F2[i][j]*Inv[j]%mod;OR(F2[i],k,1);
    }OR(F2[n],k,-1);printf("%d\n",F2[n][k-1]);
}

by 天有不测风云 @ 2021-09-18 20:19:54

评测机波动

by wssbi @ 2021-09-18 20:20:50

楼上正解

by j1ANGFeng @ 2021-09-18 20:22:50

@275307894a

你谷日爆