[数学记录]P4221 [WC2018]州区划分
command_block
2019-10-31 21:19:10
**题意** : 给出一张 $n$ 个点的无向图，有点权。
要将该图**划分**成若干个子图，满足每个子图内都没有欧拉回路。
现在小 S 要将这 $n$ 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。
将子图按一定顺序排列（不同的排列顺序被认为是不同的方案）
定义第 $i$ 个子图的权值为：第 $i$ 个州的人口在前 $i$ 个州的人口中所占比例的 $p$ 次幂。
定义一个划分的满意度为所有州的满意度的乘积，求所有合法划分方案的满意度之和。
答案对 $998244353$ 取模。
$n\leq 21$ ,时限 $\texttt{10s}$。
------------
子图满足要求的充要条件为 : 不连通或者有奇数度。
不连通 : 并查集判一下就好了。
度数 : 直接 $O(n^22^n)$ 累加暴力搞搞。
然后可以设计一个dp:
$e[S]$ 表示状态$S$ 是否合法。
$P[S]=\sum\limits_{i∈S}w[i]$
$dp[S]$ 表示已选择点集 $S$ 的总答案。
容易得到 $dp[S]=\dfrac{1}{P[S]^p}\sum\limits_{S'⊊S}dp[S-S']P[S']^pe[S']$
最后的答案是 $dp[$全集$]$。
这样需要枚举子集，复杂度是 $O(3^n)$ ,不太跑得过。
可以使用 $\rm FST$ (快速子集卷积)来优化。
这东西是子集卷积,但却是自己卷自己……
我们观察可得每个数只会卷到自己的真子集，那么按照 $|S|$ 递增的顺序来卷积就好了。
记得卷出来之后需要 $\rm IFWT$ 乘一下前面那个系数再 $\rm DWT$ 回去。
复杂度 $O(n^22^n)$。
有点卡常,别开`long long`。
```cpp
#include<algorithm>
#include<cstdio>
#define Maxn 2100000
#define mod 998244353
#define ll long long
using namespace std;
ll powM(ll a,ll t=mod-2)
{
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int n,m,p;
void DWT(int *a)
{
for (int len=1;len<n;len<<=1)
for (int p=0;p<n;p+=len+len)
for (int i=p;i<p+len;i++)
a[i+len]=(a[i]+a[i+len])%mod;
}
void IDWT(int *a)
{
for (int len=1;len<n;len<<=1)
for (int p=0;p<n;p+=len+len)
for (int i=p;i<p+len;i++)
a[i+len]=(a[i+len]-a[i]+mod)%mod;
}
int f[25],du[25][25];
int findf(int x)
{return f[x]==x ? x : f[x]=findf(f[x]);}
bool e[Maxn];
int cnt[Maxn],P[Maxn],H[Maxn],F[22][Maxn],G[22][Maxn];
int main()
{
scanf("%d%d%d",&n,&m,&p);
for (int i=0,from,to;i<m;i++){
scanf("%d%d",&from,&to);
from--;to--;
du[from][to]++;
du[to][from]++;
}for (int i=0;i<n;i++)scanf("%d",&P[1<<i]);
int lim=n; n=1<<n;
for (int i=1;i<n;i++){
cnt[i]=cnt[i>>1]+(i&1);
P[i]=P[i-(i&-i)]+P[(i&-i)];
H[i]=powM(P[i],mod-1-p);
}
for (int i=1;i<n;i++){
bool e=0;
for (int j=0;j<lim;j++)f[j]=j;
for (int j=0;j<lim;j++)if ((1<<j)&i){
int sum=0;
for (int k=0;k<lim;k++)if ((1<<k)&i){
sum+=du[j][k];
if (du[j][k])
f[findf(j)]=f[findf(k)];
}if (sum&1){e=1;break;}
}
int flag=-1;
for (int j=0;j<lim;j++)
if ((1<<j)&i){
if (flag==-1)flag=findf(j);
else if (flag!=findf(j))
{e=1;break;}
}
if (!e)P[i]=0;
else P[i]=powM(P[i],p);
}
for (int i=0;i<n;i++)
G[cnt[i]][i]=P[i];
for (int i=0;i<=lim;i++)
DWT(G[i]);
F[0][0]=1;DWT(F[0]);
for (int i=1;i<=lim;i++){
for (int j=0;j<i;j++)
for (int k=0;k<n;k++)
F[i][k]=(F[i][k]+static_cast<ll>(F[j][k])*G[i-j][k])%mod;
IDWT(F[i]);
for (int k=0;k<n;k++)
if (cnt[k]==i)
F[i][k]=static_cast<ll>(F[i][k])*H[k]%mod;
else F[i][k]=0;
if (i<lim)DWT(F[i]);
}printf("%d",F[lim][n-1]);
return 0;
}
```