Description

Input

Output

Solution

这题有好几个做法，这里介绍两个

Solution 1

（这似乎是网上的正解） From zsjzliziyang

设f[ i ][ j ]表示度数为1、2的点个数分别为i，j时答案。 分为下面的4种情况 1：当t2为0时我们新增若干条长度为2的链，我们将不会在这些链中间加其他任何点 2：新增形如1-2-1的一条新链 3：在条链的一个位置加入两个为2的点 4：把某一条链拆掉，将其中度数为2的点与3个新的点构成一个新的环 这个方法最关键的地方就是它是把一条链中间的度数为2的点和3个新的点构成一个环，很大程度上避免了在环中间加入新的数导致很难搞重复的窘境

然后进行DP即可 但因为本题有更快的方法，所以作者未打出来 详情可转至zsjzliziyang的文章

Solution 2

这解法我还是打了的[小庆幸]

Mentality

由于点的度数只有1,2两种，图的组成一定是若干条链与若干个环，设度数为1,2点的个数分别为c1,c2。

一条链两端有两个度数为1的点，于是链的条数k确定了k=c1/2（c1为奇数则无解）。

首先考虑c1个点两两匹配的方案数，考虑将c1个点放到左右两边对齐的方案，即A(c1,c1/2)，然后对齐的一对点互相交换是同一种方案，即每种方案算重复2^{(c1/2)次。综上c1个点两两匹配方案数为A(c1,c1/2)/(2}(c1/2))。

然后考虑c2个点怎么分配。枚举x表示分配x个点组成链，c2-x个点组成环，先乘上系数C(c2,x)。

设f[i]表示i个点插进k条链的方案，只需考虑i有几个位置可插。之前已经插入i-1个点，因此有i-1+k个位置可插，递推式：

f[0]=1 f[i]=f[i-1]*(i-1+k)

设g[i]表示i个点组成若干环的方案，分两种情况：1.i与前面两点新建三元环 2.i插入到之前某个环 递推式：

g[0]=1 g[i]=g[i-3]C(i-1,2)+g[i-1](i-1)

最终答案即为： sigma(f[x]*g[c2-x]*C(c2,x))

预处理阶乘逆元，组合数可以O(1)算出，f,g可以O(n)递推，答案也可O(n)计算，总复杂度O(n)

Code

#include <cstdio> #include <algorithm> #define MO 998244353 #define N 2001 #define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout); using namespace std; int i,n,a; long long ans,t,tot,p[3],f[N],g[N],inv[5001],inc[5001]; long long ksm(long long x,int y) { long long sum=1; while (y) { if (y&1)sum=sum*x%MO; x=x*x%MO; y>>=1; } return sum; } long long C(long long x,long long y) { return inv[x]*inc[y]%MO*inc[x-y]%MO; } int main() { open("graph"); inv[1]=inv[0]=1; for (i=2;i<=5000;i++) inv[i]=inv[i-1]*i%MO; inc[5000]=ksm(inv[5000],MO-2); for (i=4999;i>=0;i--) inc[i]=inc[i+1]*(i+1)%MO; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&a); p[a]++; } tot=p[1]/2; if (p[1]%2!=0) { printf("0"); return 0; } t=inc[tot]*inv[p[1]]%MO*ksm(ksm(2,tot),MO-2)%MO; f[0]=g[0]=1; for (i=1;i<=p[2];i++) { f[i]=f[i-1]*(i-1+tot)%MO; g[i]=g[i-1]*(i-1)%MO; if (i>=3) g[i]=(g[i]+g[i-3]*C(i-1,2))%MO; } for (i=0;i<=p[2];i++) ans=(ans+f[i]*g[p[2]-i]%MO*C(p[2],i)%MO)%MO; printf("%lld",t*ans%MO); return 0; }