题解 P3673 【小清新计数题】

Jμdge · 2019-07-30 20:15:53 · 题解

咱这...写份题解？（不然一堆人看完 zzq 神仙的题解之后就绕道了...）

观察可得...

这么说，首先咱得看出这是一道基于图论的计数题...

为什么说是图论？楼上 zzq 奆佬讲了，这些点的指向关系构成了一棵基环树，并且另外一个关键点，一条指向边的两个端点的真假信息是对称的：

如果第 x 句话说第 y 句话是真的，那么第 y 句话是真的的同时 x 也会是真的，反之第 x 句话也是假的

如果第 x 句话说第 y 句话是假的，那么第 y 句话是真的的同时 x 就是假的了，反之第 x 句话就是真的

于是咱给这些指向边分成黑白两类，白色表示两个端点真假性相同，黑边为不同

那么如果所有话之间的真假性不出现矛盾，就必须满足基环树上的那个环上的黑边数目是偶数

设计状态与转移

接下来咱就要考虑如何去计算一个 i 条白边， j 条黑边的基环树构造的方案数了...

那么咱先考虑环上的情况...

首先咱设环上有 a 条白边和 b 条黑边（黑边数量要为偶数，且 a+b 不能等于零），因为这些点是有编号的，所以我们直接像普通的 n=a+b 个编号点计算成环方案数就行了，那么方案数就是咱破环成链后得到的 (n-1)!

然后咱考虑连上剩下的 m=i+j-a-b 个点，这时候咱就需要用到 prufer 序列辣...

经过一系列推导后咱可以得到环上加点的方案数为： n*(n+m)^{m-1}

相关证明：这只菜鸡的博客里面第 16 条

稍微具体点，就是现在有一个长度为 n 的环和 m 个点，要加 m 条边使得它们联通，这个类似生成树计数的东西就可以用 prufer 爆掉，具体的公式上面的链接里面有

再乘上 i 个点里面选 a 个点，j 个点里面选 b 个点，那么我们就可以得到 i 条白边， j 条黑边构成的合法基环树方案为：

f[i][j]=\sum_{a+b<i+j \text{,~b是偶数}}(a+b-1)!* C_i^a C_j^b \big((a+b)·(i+j)^{i+j-a-b}\big) + [\text{j是偶数}] (i+j-1)!

这里的阶乘可以合并掉后面的 a+b ，但是出于对含义的体现，咱就没有合并

这里单独一个环的情况要特殊考虑...

这里的话，咱把后面的一小部分东西预处理了一下，就是对于长度为 n 的环和 m 个点构成基环树的方案先求出来，然后 f 直接累加即可，重新用公式表达一下就是：

g[n][m]=\begin{cases}(n-1)!* n(n+m)^{m-1} &,m>0\\ (n-1)! &,m=0 \end{cases}

f[i][j]=\sum_{a+b<=i+j \text{,~b是偶数}} C_i^a ·C_j^b· g[a+b][i+j-a-b]

这样 f 数组的求法就 ojbk 了...

统计答案

最后终于是统计答案了，因为咱发现答案图可以是多个基环树构成的基环树森林，所以我们还要爆枚转移答案：

我们令 ans[i][j] 表示答案方案数，转移还是有点奇怪的，因为我们发现答案可能算重，比如说有两个白边自环的点，我们组合数计算答案的时候会算两次，不仅仅是这种情况，不同形状的基环树之间贡献也会算重，所以我们要固定 1 号点所在的位置，然后后面的基环树就可以随意枚举转移了...

具体操作还是看代码好了...

Code

//by Judge
#include<cstdio>
#include<cstring>
#include<iostream>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define ll long long
using namespace std;
const int mod=998244353,M=53;
typedef int ARR[M][M];
char s[M]; ARR C,f,g,ans;
int n,one,zero,fac[M];
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void Pls(int& x,int y){if((x+=y)>=mod)x-=mod;}
inline int qpow(int x,int p){ Rg int s=1; if(p<=0) return 1;
    for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s;
}
int main(){ scanf("%s",s+1),n=strlen(s+1);
    fp(i,1,n) if(s[i]==48) ++zero; else ++one;
    fac[0]=1; fp(i,1,n) fac[i]=mul(fac[i-1],i);
    fp(i,0,n) C[i][0]=1;
    fp(i,1,n) fp(j,1,n) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    // i 个人构成 fake 圈， j 个人构成 fake 链 
    fp(i,1,n) fp(j,0,n-i) g[i][j]=mul(fac[i-1],mul(j?i:1,qpow(i+j,j-1)));
    // i 个人没有 fake ，j 个人 fake , a+b 个人构成 fake 圈，a 个人不 fake ，剩下的人构成 fake 链 
    fp(i,0,one) fp(j,0,zero) fp(a,0,i) for(Rg int b=0;b<=j;b+=2) if(a|b)
        Pls(f[i][j],mul(mul(C[i][a],C[j][b]),g[a+b][i+j-a-b]));
    ans[0][0]=1;
    fp(i,0,one) fp(j,0,zero) if(i|j){
        if(i) fp(a,1,i) fp(b,0,j) Pls(ans[i][j],mul(ans[i-a][j-b],mul(mul(C[i-1][a-1],C[j][b]),f[a][b])));
        else fp(b,1,j) Pls(ans[i][j],mul(ans[i][j-b],mul(mul(C[i][i],C[j-1][b-1]),f[i][b])));
    } return !printf("%d\n",ans[one][zero]);
}