题目描述:
https://www.luogu.org/problemnew/show/P4221
题解:
设 $f[S]$ 表示选集合 $S$ 时所有满意度乘积之和,$W[S]$ 表示集合 $S$ 中选中的 $w$ 之和. 显然有这样一个式子:$$f[S]= \frac{1}{W[S]^p} \sum\limits_{T \subseteq S}f[T]*W[S-T]^p*[check(S-T)]$$
后面 $check$ 的意思是判断 $S-T$ 是否合法.
原题义中不合法的条件是存在一条欧拉回路. 那么:
若图不连通则不存在.
若一个点的度数是奇数则不存在
单个点一定存在
这样可以 $O(2^nn^2)$ 处理出 $check$. 然后就是子集卷积了.
时间复杂度 $O(2^nn^2)$.
代码:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- const int N = 25;
- const int M = (1<<21)+20;
- const int MOD = 998244353;
- template<typename T>
- inline void read(T&x)
- {
- T f = 1,c = 0;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
- x = f*c;
- }
- template<typename T>inline void Mod(T&x){if(x>=MOD)x-=MOD;}
- int fastpow(int x,int y)
- {
- int ret = 1;
- while(y)
- {
- if(y&1)ret=1ll*ret*x%MOD;
- x=1ll*x*x%MOD;y>>=1;
- }
- return ret;
- }
- int inv(int x){return fastpow(x,MOD-2);}
- int n,m,p,mp[N],lg[M],cnt[M],w[N],W[M],Wp[M],iWp[M],f[N][M],g[N][M],h[M];
- void fwt(int*a,const int len,const int k)
- {
- for(int i=1;i<len;i<<=1)
- for(int j=0;j<len;j+=(i<<1))
- for(int o=0;o<i;o++)
- {
- if(k==1)Mod(a[j+o+i]+=a[j+o]);
- else Mod(a[j+o+i]+=MOD-a[j+o]);
- }
- }
- int ff[N],d[N];
- int findff(int x){return x==ff[x]?x:ff[x]=findff(ff[x]);}
- int main()
- {
- read(n),read(m),read(p);
- for(int i=2;i<=(1<<n);i<<=1)lg[i]=lg[i>>1]+1;
- for(int i=1;i<(1<<n);i++)cnt[i]=cnt[i-(i&-i)]+1;
- for(int u,v,i=1;i<=m;i++)
- {
- read(u),read(v);u--,v--;
- mp[u]|=(1<<v),mp[v]|=(1<<u);
- }
- for(int i=0;i<n;i++)read(w[i]);
- for(int i=1;i<(1<<n);i++)
- {
- for(int j=0;j<n;j++)ff[j]=j;
- for(int j=0;j<n;j++)d[j]=((i>>j)&1)?(mp[j]&i):0;
- for(int j=0;j<n;j++)if(d[j])
- {
- int now = d[j];
- while(now)
- ff[findff(lg[now&-now])]=findff(j),now-=now&-now;
- }
- bool FG = 0;int x = lg[i&-i];
- for(int j=0;j<n;j++)if((i>>j)&1)if(cnt[d[j]]&1)FG=1;
- for(int j=0;j<n;j++)if((i>>j)&1)if(findff(j)!=findff(x))FG=1;
- if(cnt[i]==1)FG = 0;
- Mod(W[i] = W[i-(i&-i)]+w[lg[i&-i]]),Wp[i]=fastpow(W[i],p);iWp[i] = inv(Wp[i]);
- if(FG)g[cnt[i]][i] = Wp[i];
- }
- f[0][0] = 1;int len = (1<<n);
- fwt(f[0],len,1);
- for(int i=1;i<=n;i++)
- {
- fwt(g[i],len,1);
- for(int j=1;j<=i;j++)
- for(int k=0;k<len;k++)
- Mod(h[k]+=1ll*f[i-j][k]*g[j][k]%MOD);
- fwt(h,len,-1);
- for(int j=0;j<len;j++)f[i][j]=1ll*h[j]*iWp[j]%MOD,h[j]=0;
- if(i!=n)fwt(f[i],len,1);
- }
- printf("%d\n",f[n][len-1]);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3121036.html