文章导读

Feb. 10th 总结 | 组合数学-计数 & Catalan数

DRheEheAM_Gary 2026-02-11 62

组合数学-计数

P6057 [加油武汉] 七步洗手法

这道题分析题目，发现直接统计行不通。

我们考虑统计全部种类的三角形减去异色三角形的个数

全部种类三角形很好求，就是 $C_n^3$ 。

异色三角形我们进行分析，发现可以统计一个点中异色的边组成的角的个数。
因为两个异色角可以组成一个异色三角形，并且 一个异色角只会包含在一个异色三角形中 。

最后将上面统计的异色角个数除以 2 ，再相减即可。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10;
int n,m,dg[N];
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        dg[u]++;
        dg[v]++;
    }
    int ans=0;
    for (int i=1;i<=n;i++) {
        ans+=(dg[i])*(n-1-dg[i]);
    }
    cout<<(n*(n-1)*(n-2)/6-ans/2);
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10;
int n,m,dg[N];
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        dg[u]++;
        dg[v]++;
    }
    int ans=0;
    for (int i=1;i<=n;i++) {
        ans+=(dg[i])*(n-1-dg[i]);
    }
    cout<<(n*(n-1)*(n-2)/6-ans/2);
    return 0;
}

P6561 [SBCOI2020] 人

我可以友情客串一下：见ooliver的这篇博客

但是我也要写一下（

我们分析题目，发现可以将第 $2i-1$ 与第 $2i$ 个放在一组中看。

然后题目中的序列便可以转换为一个长度为 $m$ 字符串 $S$ ，其中 $S_i\in\{A,B,C\}$

然后这个字符串中：

A ：选择奇数，即 $2i-1$ ；
B ：选择偶数，即 $2i$ ；
C ：不选。

那么问题就转换为了这样一个字符串，其中 A 的个数为 $a$ ，B 的个数为 $b$ ，有多少种可能。

显然可以发现，BA 是不可行的方案。

那么也就是说，对于两个 C 之间的 A 和 B ，只存在一种排列，即为 AAAA...BBBB...

那么在两个 C 之间的 AB 排列唯一。

所以考虑，在 $m-a-b$ 个 C 之间放 A 和 B 。

发现是插板法的第二种形式。

故答案为：

\large \begin{pmatrix} m-a\\ m-a-b \end{pmatrix} \cdot \begin{pmatrix} m-b\\ m-a-b \end{pmatrix}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10,mod=998244353;
int m,a,b,f[N],invf[N];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) (res*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return res;
}
int C(int n,int m) {
    return (((f[n]*invf[m])%mod)*invf[n-m])%mod;
}
signed main() {
    Cios;
    f[0]=f[1]=1;
    for (int i=2;i<N;i++) f[i]=(i*f[i-1])%mod;
    invf[N-1]=qpow(f[N-1],mod-2);
    for (int i=N-2;i>=0;i--) invf[i]=((i+1)*invf[i+1])%mod;
    int T;
    cin>>T;
    while (T--) {
        cin>>m>>a>>b;
        cout<<((C(m-a,m-a-b)*C(m-b,m-a-b))%mod)<<endl;
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10,mod=998244353;
int m,a,b,f[N],invf[N];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) (res*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return res;
}
int C(int n,int m) {
    return (((f[n]*invf[m])%mod)*invf[n-m])%mod;
}
signed main() {
    Cios;
    f[0]=f[1]=1;
    for (int i=2;i<N;i++) f[i]=(i*f[i-1])%mod;
    invf[N-1]=qpow(f[N-1],mod-2);
    for (int i=N-2;i>=0;i--) invf[i]=((i+1)*invf[i+1])%mod;
    int T;
    cin>>T;
    while (T--) {
        cin>>m>>a>>b;
        cout<<((C(m-a,m-a-b)*C(m-b,m-a-b))%mod)<<endl;
    }
    return 0;
}

P4163 [SCOI2007] 排列

考虑状压 dp

定义 dp 数组 $dp[i][k]$ ，其中 $i$ 为状态压缩，第 $j$ 位的 $0/1$ 是取或不取； $k$ 表示这个数 $\bmod d$ 后余 $k$ 。

那么状态转移方程： $dp[i|(1<<j)][(k\times10+s[j])\bmod d]+=dp[i][k]$

答案即为 $dp[1<<n][0]$ …吗？

没错。我们统计时并没有去掉重复数字带来的干扰。
答案需要除以每个重复数字出现次数的全排列 ( $cnt_i!$ )。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc S=10,N=1e3+10;
string s;
int d,dp[(1<<S)+5][N],cnt[S],h,ans,er;
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        cin>>s>>d;
        int n=s.size();
        memset (dp,0,sizeof dp);
        dp[0][0]=1;
        for (int i=0;i<(1<<n);i++) {
            for (int j=0;j<n;j++) {
                if ((i>>j)&1) continue;
                for (int k=0;k<d;k++) dp[i|(1<<j)][(k*10+s[j]-'0')%d]+=dp[i][k];
            }
        }
        memset (cnt,0,sizeof cnt);
        for (int i=0;i<n;i++) cnt[s[i]-'0']++;
        ans=dp[(1<<n)-1][0];
        for (int i=0;i<10;i++) {
            for (int j=2;j<=cnt[i];j++) ans/=j;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc S=10,N=1e3+10;
string s;
int d,dp[(1<<S)+5][N],cnt[S],h,ans,er;
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        cin>>s>>d;
        int n=s.size();
        memset (dp,0,sizeof dp);
        dp[0][0]=1;
        for (int i=0;i<(1<<n);i++) {
            for (int j=0;j<n;j++) {
                if ((i>>j)&1) continue;
                for (int k=0;k<d;k++) dp[i|(1<<j)][(k*10+s[j]-'0')%d]+=dp[i][k];
            }
        }
        memset (cnt,0,sizeof cnt);
        for (int i=0;i<n;i++) cnt[s[i]-'0']++;
        ans=dp[(1<<n)-1][0];
        for (int i=0;i<10;i++) {
            for (int j=2;j<=cnt[i];j++) ans/=j;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Catalan数

上面有个链接，关于 Catalan 数的定义参见 oi-wiki。

简化后有以下四个式子：

\large C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1} \ (n>0,C_0=1)\\

\large C_n=\frac{1}{n+1}C_{2n}^{n}=\frac{(2n)!}{n!(n+1)!}\ (n\ge0)\\

\large C_n=C_{2n}^{n}-C_{2n}^{n+1}\ (n\ge0)\\

\large C_n=\frac{4n-2}{n+1}C_{n-1}\ (n>0,C_0=1)\\

关于这四个式子的相互推导也可以参见oi-wiki，这里不再赘述。

来看两道例题：

P1976 鸡蛋饼

这道题就是 Catalan 数的基础应用：圆内不相交弦个数。

答案直接为 Catalan 数。

因为 $n$ 较大，但是有模数，我们用第二个式子，预处理阶乘及其逆元直接计算。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=3000,mod=1e8+7;
int n,f[N*2],invf[N*2];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
} 
signed main() {
    Cios;
    f[0]=f[1]=1;
    for (int i=2;i<(N*2);i++) f[i]=(i*f[i-1])%mod;
    invf[(N*2)-1]=qpow(f[(N*2)-1],mod-2);
    for (int i=(N*2)-2;i>=0;i--) invf[i]=((i+1)*invf[i+1])%mod;
    cin>>n;
    cout<<((f[2*n]*invf[n])%mod*invf[n+1])%mod;
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=3000,mod=1e8+7;
int n,f[N*2],invf[N*2];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
} 
signed main() {
    Cios;
    f[0]=f[1]=1;
    for (int i=2;i<(N*2);i++) f[i]=(i*f[i-1])%mod;
    invf[(N*2)-1]=qpow(f[(N*2)-1],mod-2);
    for (int i=(N*2)-2;i>=0;i--) invf[i]=((i+1)*invf[i+1])%mod;
    cin>>n;
    cout<<((f[2*n]*invf[n])%mod*invf[n+1])%mod;
    return 0;
}

P1754 球迷购票问题

乍一看似乎无从下手。

但是我们分析一下，设序列为 $S$ ：

因为只有 $\forall i$ ，保证 $i$ 前面 50 元的人个数始终大于等于 100 元的人个数时解才合法。

而这正是 Catalan 数的基本意义之一：对于两个属性，在一段前缀中，其中一个属性的个数始终大于等于另一个属性的个数是，这种排列的个数为 Catalan 数。

因为 $n$ 比较小，但是没有模数，我们使用第四个式子防止溢出。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int n;
signed main() {
    Cios;
    cin>>n;
    int res=1;
    for (int i=1;i<=n;i++) res=res*(4*i-2)/(i+1);
    cout<<res;
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int n;
signed main() {
    Cios;
    cin>>n;
    int res=1;
    for (int i=1;i<=n;i++) res=res*(4*i-2)/(i+1);
    cout<<res;
    return 0;
}

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

[填写昵称邮箱后可以评论]

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 10th 总结 | 组合数学-计数 & Catalan数

组合数学-计数

P6057 [加油武汉] 七步洗手法

P6561 [SBCOI2020] 人

P4163 [SCOI2007] 排列

Catalan数

P1976 鸡蛋饼

P1754 球迷购票问题

评论（0）

发表评论取消回复

插入代码

DRheEheAM_Gary Blog

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 10th 总结 | 组合数学-计数 & Catalan数

组合数学-计数

P6057 [加油武汉] 七步洗手法

P6561 [SBCOI2020] 人

P4163 [SCOI2007] 排列

Catalan数

P1976 鸡蛋饼

P1754 球迷购票问题

评论（0）

发表评论 取消回复

插入代码

DRheEheAM_Gary Blog

发表评论取消回复