组合数学与计数 DP

这东西博大精深……

前置内容

排列组合

$n$ 个数的排列：将这些数放在一个序列中，与这些数的顺序有关。 例如， $1,2,3$ 和 $3,2,1$ 是不同的排列。

$n$ 个数的组合：将这些数放在一个可重集中，与这些数的顺序无关。 例如， $\{1,2,3\}$ 和 $\{1,3,2\}$ 是同一个组合。

$A_n^m$ ，表示从 $n$ 个不同的数中选 $m$ 个数进行排列的方案数。

$C_n^m$ ，表示从 $n$ 个不同的数中选 $m$ 个数进行组合的方案数。

引理 1 ：

$$A_n^m=\frac{n!}{(n-m)!}$$

$$C_n^m=\frac{n!}{m!(n-m)!}$$

证明：

$A_n^m$ 可以看作将 $n$ 个不同的数选 $m$ 个数放在一个长度为 $m$ 的序列上。序列的顺序重要。 所以第一个位置上可以放 $n$ 个数中任意一个，共 $n$ 中方案。第二个位置上只有 $n-1$ 个数中任意一个，因为有一个已经被第一个位置选走了，共 $n-1$ 中方案……这些位置的选择相互独立，所以用乘法原理，可得 $A_n^m=\displaystyle\prod_{i=0}^{m-1} (n-i)=\frac{n!}{(n-m)!}$ 。

而 $C_n^m$ 可以看作 $\frac{A_n^m}{A^m_m}=\frac{n!}{m!(n-m)!}$ ，因为组合的顺序不重要，所以要把序列 $m$ 的排列数去除。

容斥原理

容斥原理 I

已知有 $n$ 个事件，每个事件的方案数为 $x_i$ ，求所有事件至少发生了一个的方案数。

根据直觉，先累加 $\displaystyle\sum_i x_i$ ，然后我们就会发现这样重算了，例如当 $1$ 和 $2$ 同时发生时，他会在 $1$ 中和 $2$ 中分别统计一遍。同理，我们需要减去 $\displaystyle\sum_{i,j} x_i \cap x_j$ 。但是这样， $1,2,3$ 同时发生时，它会被 $1,2$ 和 $2,3$ 和 $1,3$ 减去，会被 $1$ 和 $1,3$ 和 $2,3$ 累加，最后少加了一次，所以应该加上。同理，我们也要加上 $\displaystyle\sum_{i,j,k} x_i \cap x_j \cap x_k$ ……

最终，我们得到了这样的公式：

$$|\cup_{i=1}^n x_i|=\sum_{S} |\cap_{j \in S} x_j|$$

容斥原理 II

已知有 $n$ 个事件，每个事件的方案数为 $x_i$ ，求所有事件同时发生了的方案数。

事实上，这等价于求 $U-|\cup_{i=1}^n \overline{x_i}|$ ，其中 $U$ 为全集（下文如无特指，均为此意义），即这些事件不发生的事件至少发生一个的方案数是不合法的方案，要减去。

这就是容斥原理第二个公式：

$$|\cap_{i=1}^n x_i|=|U-\cup_{i=1}^n \overline{x_i}|$$

组合数基本定律

组合数基本定律（下称基本定律）：

方程 $\displaystyle\sum_{i=1}^n x_i=m(x_i>0)$ 的整数解的个数为 $C_{m-1}^{n-1}$ 。

证明：

可以看作有 $m$ 个位置，然后需要将这 $m$ 个位置划分成 $n$ 个非空连续段，第 $i$ 个连续段的长度为 $x_i$ 的值。

那么，可以看作有 $n-1$ 个挡板把 $m$ 个位置进行非空划分。进一步的，每个挡板只能在 $m-1$ 个缝隙中插入，且不能有两个挡板占据同一个位置。

这也就是，从 $m-1$ 个缝隙中，选出 $n-1$ 个缝隙，进行组合，这是因为挡板之间没有顺序。

那么这样，答案就是 $C_{m-1}^{n-1}$ 。

衍生推论

方程 $\displaystyle\sum_{i=1}^n x_i=m(x_i\ge 0)$ 的整数解的方案数为 $C_{n+m-1}^{m-1}$ 。

可以令 $y_i=x_i+1$ ，那么原问题就变成了方程 $\displaystyle\sum_{i=1}^n y_i=m+n(y_i\ge 1)$ 的整数解的方案数。

由基本定律得 $C_{n+m-1}^{m-1}$ 。

事实上，这个可以扩展到方程 $\displaystyle\sum_{i=1}^n x_i=m(x_i\ge m_i)$ 的整数解的方案数。只需要容斥之后，按照上面的代换即可。

概率

题目描述：

你有一个随机生成器，每次会均匀随机地生成一个 $[0,m]$ 之间的整数。你用这个随机生成器生成了 $2n$ 个整数，你想知道你生成的前 $n$ 个整数的和比后 $n$ 个整数的和大的概率是多少。

你只需求出这个概率对质数 $P$ 取模后的结果即可。

$n,m \le 2000,10^8 \le P \le 10^9$ ，数据组数不超过 $2000$ 组。

事实上，前 $n$ 个数的和和后 $n$ 个数的关系只有三种：相等，大和小。

其中，大和小的情况数是完全对应相等的，因为每一种前 $n$ 个数的和比后 $n$ 个数大的方案，进行反转后就是一种前 $n$ 个数的和比后 $n$ 个数小的方案。

所以，设相等的方案数为 $x$ ，则答案为 $\frac{(m+1)^{2n}-x}{2(m+1)^{2n}}$ 。

考虑如何求解相等的方案数。

设第 $i$ 个数为 $i$ ，则有：

$$\sum_{i=1}^n x_i=\sum_{i=n+1}^{2n} x_i(0 \le x_i \le m)$$

$$\sum_{i=1}^n x_i-\sum_{i=n+1}^{2n} x_i=0(0 \le x_i \le m)$$

$$\sum_{i=1}^n x_i+\sum_{i=n+1}^{2n} -x_i=0(0 \le x_i \le m)$$

令 $n+1\le i \le 2n$ 时， $y_i=-x_i$ ，否则 $y_i=x_i$ ，则有：

$$\sum_{i=1}^{2n} y_i=0$$

其中对于 $1 \le i \le n,0 \le y_i \le m$ ，否则 $-m \le y_i \le 0$ 。

这里有负数，不是很好处理。考虑令 $z_i=y_i+m$ ，则有：

$$\sum_{i=1}^n y_i+\sum_{i=n+1}^{2n} z_i=nm(0 \le z_i,y_i \le m)$$

这是一个可以处理的形式了。容斥和基本定律即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
using namespace std;
const int N=4000010;
int T,P,n,m,fac[N],inv[N];
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
int C(int n,int m){
    if(n<m)return 0;
    return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
    scanf("%d%d",&P,&T);
    const int inv2=(P+1)>>1;
    fac[0]=1;
    for(int i=1;i<=4000000;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[4000000]=kpow(fac[4000000],P-2);
    for(int i=3999999;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
    while(T--){
        scanf("%d%d",&n,&m);
        int res=0;
        for(int i=0;i<=2*n;i++){
            int t=1ll*C(2*n,i)*C(2*n-1+n*m-i*(m+1),2*n-1)%P;
            if(i&1)(res+=P-t)%=P;
            else (res+=t)%=P;
        }
    printf("%d\n",1ll*(kpow(m+1,2*n)-res+P)%P*kpow(m+1,P-2*n-1)%P*inv2%P);
    }
    return 0;
}

前置知识

钦定

注意区分钦定和至少。

在一个可重集 $S$ 中或序列中钦定 $k$ 个元素满足性质 A ，为选择 $k$ 个满足元素后，其余元素任意的方案数。

举个例子，在一个长度为 $3$ 的序列中每个数随机生成 $[1,2]$ 中的数，则至少有一个元素为偶数的情况为：

$$[2,1,1],[2,2,1],[2,1,2],[2,2,2],[1,2,1],[1,2,2],[1,1,2]$$

钦定有一个元素为偶数的情况数为：

选择第 $1$ 个数满足为偶数的情况数：

$$[2,1,1],[2,1,2],[2,2,1],[2,2,2]$$

选择第 $2$ 个数满足为偶数的情况数：

$$[1,2,1],[1,2,2],[2,2,1],[2,2,2]$$

选择第 $3$ 个数满足为偶数的情况数：

$$[1,1,2],[1,2,2],[2,1,2],[2,2,2]$$

总情况为：

$$[1,1,2],[1,2,2],[2,1,2],[2,2,2],[1,2,1],[1,2,2],[2,2,1],[2,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]$$

二项式反演

一般的，在一个长度为 $n$ 个集合或序列中，若 $f(k)$ 为恰好有 $k$ 个满足条件的数的方案数， $g(k)$ 为钦定有 $k$ 个满足条件的数的方案数，若已知 $f(k)$ 则有：

$$g(k)=\sum_{i=k}^n C_i^kf(k)$$

若已知 $g(k)$ 则有：

$$f(k)=\sum_{i=k}^n (-1)^{i-k} C_i^kg(k)$$

P1287 盒子与球

题目： 盒子与球 。

题目描述：

现有 $r$ 个互不相同的盒子和 $n$ 个互不相同的球，要将这 $n$ 个球放入 $r$ 个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。

$n,r \le 10$ 。

定义 $f(k)$ 为恰好有 $k$ 个空盒子的方案数， $g(k)$ 为钦定有 $k$ 个盒子的方案数，则我们要求 $f(0)$ 。

根据定义容易有 $g(k)=(r-k)^n$ 。

直接二项式反演即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=10010;
int n,r,ans;
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=t*a;
        a=a*a;
        b>>=1;
    }
    return t;
}
signed main(){
    cin>>n>>r;
    int f=1;
    int C=1;
    for(int i=0;i<r;i++){
        ans+=f*kpow(r-i,n)*C;
        f*=-1;
        C*=(r-i);
        C/=(i+1);
    }
    cout<<ans;
    return 0;
}

P4491 [HAOI2018] 染色

题目： [HAOI2018] 染色 。

题目描述：

为了报答小 C 的苹果，小 G 打算送给热爱美术的小 C 一块画布，这块画布可以抽象为一个长度为 $N$ 的序列，每个位置都可以被染成 $M$ 种颜色中的某一种。

然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数，如果恰好出现了 $S$ 次的颜色有 $K$ 种，则小 C 会产生 $W_k$ 的愉悦度。

小 C 希望知道对于所有可能的染色方案，他能获得的愉悦度的和对 $1004535809$
取模的结果是多少。

$n\le 10^7,m\le 10^5,s\le 150$ 。

定义 $f(k)$ 为恰好有 $k$ 个颜色出现次数为 $S$ 的方案数， $g(k)$ 为钦定有 $k$ 个颜色出现次数为 $S$ 的方案数。

考虑计算 $g(k)$ 。

那么首先我们要从 $m$ 个颜色中选出 $k$ 个，方案数 $C_m^k$ 。

其次，我们要从 $n$ 个位置中选 $kS$ 个位置染色，这样的方案数为 $C_n^{kS}$ 。

接着，我们要给 $kS$ 个染 $k$ 种颜色，每种颜色恰好出现 $S$ 次，方案数为 $\frac{(kS)!}{(S!)^k}$ 。

最后，其余位置任选，方案数为 $(n-kS)^{m-k}$ 。

所以，我们有：

$$g(k)=C_m^kC_n^{kS}(n-kS)^{m-k}\times \frac{(kS)!}{(S!)^k}$$

然后就能愉快的二项式反演了。

注意这题对于每个 $k$ ，都要求 $f(k)$ ，同时 $m \le 10^5$ 。

容易发现二项式反演的式子是一个减法卷积形式，可以用 FFT 加速计算。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <bits/stdc++.h>
using namespace std;
const int N=300100,P=1004535809,M=2e7+10;
int n,m,s,w[N],a[N],b[N],fac[M],inv[M],r[N],len,l;
int kpow(int a,int b){
    if(b<0)return 0;
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
int C(int n,int m){
    if(n<m)return 0;
    return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
void NTT(int *f,int t){
    for(int i=0;i<len;i++)if(i<r[i])swap(f[i],f[r[i]]);
    for(int i=2;i<=len;i<<=1){
        int G=kpow((t==1?3:kpow(3,P-2)),(P-1)/i);
        for(int j=0;j<len;j+=i){
            int g=1;
            for(int k=j;k<j+(i>>1);k++){
                int x=f[k],y=1ll*g*f[k+(i>>1)]%P;
                f[k]=(x+y)%P;
                f[k+(i>>1)]=(x-y+P)%P;
                g=1ll*g*G%P;
            }
        }
    }
    if(t==-1){
        int in=kpow(len,P-2);
        for(int i=0;i<len;i++)f[i]=1ll*f[i]*in%P;
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=0;i<=m;i++)cin>>w[i];
    fac[0]=1;
    for(int i=1;i<=2e7;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[(int)2e7]=kpow(fac[(int)2e7],P-2);
    for(int i=(int)(2e7)-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
    for(int i=0;i<=m;i++){
        a[i]=1ll*C(m,i)*C(n,s*i)%P*kpow(m-i,n-s*i)%P*fac[i*s]%P*kpow(inv[s],i)%P*fac[i]%P;
    }
    reverse(a,a+m+1);
    len=1,l=0;
    while(len<=2*m)len<<=1,l++;
    for(int i=0;i<len;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i<=m;i++){
        if(i&1)b[i]=(P-inv[i]);
        else b[i]=inv[i];
    }
    NTT(a,1);NTT(b,1);
    for(int i=0;i<len;i++)a[i]=1ll*a[i]*b[i]%P;
    NTT(a,-1);
    reverse(a,a+m+1);
    int res=0;
    for(int i=0;i<=m;i++){
        (res+=1ll*inv[i]*a[i]%P*w[i]%P)%=P;
    }
    cout<<res;
    return 0;
}

P5339 [TJOI2019] 唱、跳、rap和篮球

题目： [TJOI2019] 唱、跳、rap和篮球 。

题目描述：

学院要组织学生参观，要求学生们排成一队进行参观。他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢 rap ，还有一部分最喜欢篮球。如果队列中 $k$, $k + 1$, $k + 2$, $k + 3$ 位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢 rap 、最喜欢篮球，那么他们就会聚在一起讨论。大中锋不希望这种事情发生，因为这会使得队伍显得很乱。大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。由于合法的队伍可能会有很多种，种类数对 $998244353$ 取模。

有 $a$ 个人最喜欢唱， $b$ 个人最喜欢跳， $c$ 个人最喜欢 rap ， $d$ 个人最喜欢篮球，大中峰要组织 $n$ 个人参观。

$n \le 1000$ ， $a,b,c,d \le 500$ 。

定义 $f(k)$ 为恰好有 $k$ 组同学讨论的方案数， $g(k)$ 为钦定有 $k$ 组同学讨论的方案数，则我们要求 $f(0)$ 。

考虑怎么求 $g(k)$ 。

$g(k)$ 分为独立的两部分：选择不相交的 $k$ 组长度为 $4$ 的连续位置，以及从 $a-k,b-k,c-k,d-k$ 中选择 $n-4k$ 个人占据 $n-4k$ 个位置的方案数。

先看第一部分。这个较为简单，可以直接 DP 求解：令 $f_{i,j}$ 表示在长度为 $i$ 的序列中选 $j$ 组不交连续 $4$ 个位置的方案数，则有 $f_{i,j}=f_{i-1,j}+f_{i-4,j-1}$ 。

再看第二部分。这部分只能枚举： $\displaystyle\sum_A\sum_B\sum_C [0\le n-4k-A-B-C\le d-k]C_{n-4k}^AC_{n-4k-A}^BC_{n-4k-A-B}^C$ 。

直接转移复杂度爆炸。

我们考虑优化，令：

$$g_{i,m}=\sum_A\sum_B\sum_C C_{m}^AC_{m-A}^BC_{m-A-B}^C( \text{限制范围为} a-i,b-i,c-i,d-i)$$

$$f_{i,m}=\sum_B\sum_C C_m^BC_{m-B}^C( \text{限制范围为} a-i,b-i,c-i,d-i)$$

$$h_{i,m}=\sum_C C_m^C( \text{限制范围为} a-i,b-i,c-i,d-i)$$

容易发现 $h_{i,m}$ 可以 $O(n^3)$ 转移， $f_{i,m}$ 和 $g_{i,m}$ 分别可以用 $h_{i,m}$ 和 $f_{i,m}$ 完成 $O(n^3)$ 转移。

那么第二部分答案就是 $g_{k,n-4k}$ 。

最后二项式反演即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <bits/stdc++.h>
using namespace std;
const int N=2010,P=998244353;
int n,a,b,c,d,fac[N],inv[N],f[N][N],g[N][N],A[N],h[N][N],r[N][N];
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
int C(int n,int m){
    if(n<m)return 0;
    return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
    cin>>n>>a>>b>>c>>d;
    fac[0]=1;
    for(int i=1;i<=2000;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[2000]=kpow(fac[2000],P-2);
    for(int i=1999;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
    for(int k=0;k<=n;k++){
        if(a-k<0||b-k<0||c-k<0||d-k<0)continue;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=c-k;j++){
                if(i-j<0||i-j>d-k)continue;
                (h[k][i]+=C(i,j))%=P;
            }
        }
    }
    for(int k=0;k<=n;k++){
        if(a-k<0||b-k<0||c-k<0||d-k<0)continue;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=b-k;j++){
                if(i-j<0)continue;
                (f[k][i]+=1ll*C(i,j)*h[k][i-j]%P)%=P;
            }
        }
    }
    for(int k=0;k<=n;k++){
        if(a-k<0||b-k<0||c-k<0||d-k<0)continue;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=a-k;j++){
                if(i-j<0)continue;
                (g[k][i]+=1ll*C(i,j)*f[k][i-j]%P)%=P;
            }
        }
    }
    r[0][0]=1;
    for(int i=1;i<=n;i++){
        r[i][0]=1;
        for(int j=1;j<=n;j++){
            r[i][j]=r[i-1][j];
            if(i>=4)(r[i][j]+=r[i-4][j-1])%=P;
        }
    }
    for(int i=0;i<=n;i++){
        if(n-4*i<0)continue;
        A[i]=1ll*r[n][i]*g[i][n-4*i]%P;
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        if(i&1)ans=(ans-A[i]+P)%P;
        else (ans+=A[i])%=P;
    }
    cout<<ans;
    return 0;
}

P6478 [NOI Online #2 提高组] 游戏

题目： [NOI Online #2 提高组] 游戏 。

题目描述：

小 A 和小 B 正在玩一个游戏：有一棵包含 $n=2m$ 个点的有根树（点从 $1\sim n$ 编号），它的根是 $1$ 号点，初始时两人各拥有 $m$ 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点，若对手的点在自己的点的子树内，则该回合自己获胜；若自己的点在对方的点的子树内，该回合自己失败；其他情况视为平局。游戏共进行 $m$ 回合。

对于 $k=0,1,2,\cdots,m$，计算出非平局回合数为 $k$ 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 $x$，小 B 在 $x$ 被小 A 选择的那个回合所选择的点不同。

由于情况总数可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

$n\le 5000$ 。

定义 $f(k)$ 为恰好非平局回合数为 $k$ 的方案数， $g(k)$ 为钦定非平局回合数为 $k$ 的方案数。

$g(k)$ 可以用树形背包 $O(n^2)$ 求出。最后二项式反演就行。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <bits/stdc++.h>
using namespace std;
const int N=5010,P=998244353;
int n,a[N],sz[N],SZ[N],f[N][N],tmp[N],res[N],fac[N],inv[N];
vector<int>v[N];
void dfs(int x,int fa){
    sz[x]=1;SZ[x]=a[x];
    f[x][0]=1;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        for(int i=0;i<=sz[x]+sz[u];i++)tmp[i]=0;
        for(int j=0;j<=min(sz[x],n/2);j++){
            for(int k=0;k<=min(n/2-j,sz[u]);k++){
                (tmp[j+k]+=1ll*f[x][j]*f[u][k]%P)%=P;
            }
        }
        for(int i=0;i<=sz[x]+sz[u];i++)f[x][i]=tmp[i];
        sz[x]+=sz[u];SZ[x]+=SZ[u];
    }
    for(int i=min(SZ[x],sz[x]-SZ[x]);i>=1;i--)(f[x][i]+=1ll*f[x][i-1]*(max((a[x]?sz[x]-SZ[x]:SZ[x])-(i-1),0))%P)%=P;
}
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
int C(int n,int m){
    if(n<m)return 0;
    return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
    cin>>n;
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=kpow(fac[n],P-2);
    for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for(int i=0;i<=n/2;i++)f[1][i]=1ll*f[1][i]*fac[n/2-i]%P;
    for(int i=0;i<=n/2;i++){
        for(int j=i;j<=n/2;j++){
            if((j-i)&1)res[i]=(res[i]-1ll*C(j,i)*f[1][j]%P+P)%P;
            else res[i]=(res[i]+1ll*C(j,i)*f[1][j]%P)%P;
        }
    }
    for(int i=0;i<=n/2;i++)cout<<res[i]<<"\n";
    return 0;
}

P4921 [MtOI2018] 情侣？给我烧了！

题目： [MtOI2018] 情侣？给我烧了！ 。

题目描述：

有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2×n$ 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 $2 × n$ 个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出当 $k = 0, 1, ... , n$ 时，共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2n)!$ 种不同的就坐方案。

由于结果可能较大，因此输出对 $998244353$ 取模的结果。

$n\le 10^3$ 。

定义 $f(k)$ 为恰好 $k$ 对情侣和睦的方案数， $g(k)$ 为钦定 $k$ 对情侣和睦的方案数。

考虑求 $g(k)$ 。

首先，要从 $n$ 对情侣中选出 $k$ 对，方案数为 $C_n^k$ 。

然后，要从 $n$ 排位置中选出 $k$ 个分配给 $k$ 对情侣，方案数为 $C_n^kk!$ 。

接着，每对同一排情侣的顺序任意，方案数 $2^k$ 。

最后，其余情侣位置任意，方案数 $(2n-2k)!$ 。

所以，我们有：

$$g(k)=(C_n^k)^2k!2^k((2n-2k)!)$$

最后就可以愉快的二项式反演了！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
using namespace std;
const int N=2010,P=998244353;
int n,T,fac[N],inv[N],pw[N],a[N],xj[N][N];
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
int C(int n,int m){
    if(n<m)return 0;
    return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
    fac[0]=1;
    for(int i=1;i<=2000;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[2000]=kpow(fac[2000],P-2);
    for(int i=1999;i>=0;i--)inv[i]=1ll*(i+1)*inv[i+1]%P;
    pw[0]=1;
    for(int i=1;i<=2000;i++)pw[i]=2ll*pw[i-1]%P;
    for(int i=0;i<=1000;i++){
        for(int j=i;j<=1000;j++){
            xj[i][j]=1ll*((j-i)&1?P-1:1)*C(j,i)%P;
        }
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int j=0;j<=n;j++)a[j]=1ll*C(n,j)*C(n,j)%P*fac[j]%P*pw[j]%P*fac[2*n-2*j]%P;
        for(int i=0;i<=n;i++){
            int res=0;
            for(int j=i;j<=n;j++){
                (res+=1ll*a[j]*xj[i][j]%P)%=P;
            }
            printf("%d\n",res);
        }
    }
    return 0;
}

子集反演

定义 $f(S)$ 为集合内的点满射到 $S$ 的方案数， $g(S)$ 为集合内的点映射到 $S$ 的方案数。

一般的，若已知 $f(S)$ ，有：

$$g(S)=\sum_{T \subseteq S}f(T)$$

若已知 $g(S)$ ，有：

$$f(S)=\sum_{T \subseteq S} (-1)^{|S|-|T|}g(T)$$

P3349 [ZJOI2016] 小星星

题目： [ZJOI2016] 小星星 。

题目描述：

小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 $n$ 颗小星星，用 $m$ 条彩色的细线串了起来，每条细线连着两颗小星星。

有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 $n-1$ 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。

$n\le 17$ 。

定义 $f_{x,i,S}$ 为 $x$ 子树内的点满射到 $S$ 的方案数，其中 $x$ 映射到 $i$ 。 $g_{x,i,S}$ 为 $x$ 子树内的点映射到 $S$ 的方案数，其中 $x$ 映射到 $i$ 。

由于 $g_{x,i,S}$ 是映射，没有排列的限制，所以对于每个 $S$ ，可以简单 $O(n^3)$ 解出。

最后子集反演即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <bits/stdc++.h>
using namespace std;
const int N=18;
#define bt(x) __builtin_popcount(x)
int n,m,lst;
#define ull unsigned long long
ull f[N][N],a[1<<N];
vector<int>v[N],V[N];
void dfs(int x,int fa){
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
    }
    for(int i=1;i<=n;i++){
        if((lst>>i-1)&1^1)continue;
        f[x][i]=1;
        for(int j:v[x]){
            if(j==fa)continue;
            ull sum=0;
            for(int k:V[i]){
                if(((lst>>k-1)&1)^1)continue;
                sum+=f[j][k];
            }
            f[x][i]*=sum;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=0;i<(1<<n);i++){
        lst=i;
        dfs(1,0);
        for(int j=1;j<=n;j++)if((i>>j-1)&1)a[i]+=f[1][j];
    }
    ull sum=0;
    for(int i=0;i<(1<<n);i++){
        sum+=((n-bt(i))&1?-1:1)*a[i];
    }
    cout<<sum;
    return 0;
}

完结撒花！