command_block 的博客

command_block 的博客

[数学记录]P4221 [WC2018]州区划分

posted on 2019-10-31 21:19:10 | under 记录 |

题意 : 给出一张 $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

#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;
}