计数问题2

ooliver的头像 发布于 2026-02-10 189 次阅读 OI

计数问题2

一些公式

吸收/提取恒等式：i⋅(i−1j−1)=j⋅(ji)i \cdot \binom{i-1}{j-1} = j \cdot \binom{j}{i}

上指标反转：(rk)=(−1)k(k−r−1k)\binom{r}{k} = (-1)^k \binom{k-r-1}{k}

范德蒙德卷积公式：∑k(rm+k)(sn−k)=(r+sm+n)\sum_k \binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}

上指标卷积公式：∑k=0n(ka)(n−kb)=(n+1a+b+1)\sum_{k=0}^n \binom{k}{a} \binom{n-k}{b} = \binom{n+1}{a+b+1}

奇怪的分组

板子，没啥好说的，代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
const int mod=1e9+7;
int m,n,x,c;
int inv[N],ninv[N];

int mi(int x,int y){
	int res=1;
	while(y){
		if(y&1) (res*=x)%=mod;
		y>>=1,(x*=x)%=mod; 
	}
	return res;
}

void init(){
    inv[0]=ninv[0]=1;
    for(int i=1;i<N;i++){
		inv[i]=(i*inv[i-1])%mod;
		ninv[i]=(mi(i,mod-2)*ninv[i-1])%mod;
	}
}

int C(int x,int y){
    return inv[x]*ninv[y]%mod*ninv[x-y]%mod;
}

signed main(){
    init();
	scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++) scanf("%lld",&x),c+=x;
    printf("%lld",C(n-c-1,m-1));
	return 0;
}

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

考虑容斥，计算异色三元环，发现每个异色三元环会有两个异色角，统计所有异色角的个数，除以二，减掉就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e6+100;
int solve(int n){
    return n*(n-1)*(n-2)/6;
}
long long n,m,ans,cnt;
int u[N];
signed main(){
    cin>>n>>m;
    ans=solve(n);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        u[x]++;
        u[y]++;
    }
    for(int i=1;i<=n;i++){
        cnt+=((u[i])*(n-u[i]-1));
    }
    cout<<ans-cnt/2<<endl;
}

P4163 [SCOI2007] 排列

状压 DP，状态表示当前选择的方案，再加一维余数就行。

注意统计后要除以每个数的全排列方案数，去除重复计算的。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
int T;
char s[15];
int n,d;
int dp[(1<<11)][1005],a[15],cnt[10],pre[15];

void solve(){
    memset(dp,0,sizeof dp);
    memset(cnt,0,sizeof cnt);
    dp[0][0]=1;
    scanf("%s%d",s,&d);
    n=strlen(s);
    for(int i=0;i<n;i++) a[i+1]=s[i]-'0',cnt[a[i+1]]++;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<d;j++)
            for(int k=0;k<n;k++)
                if(!(i&(1<<k))) dp[i|(1<<k)][(j*10+a[k+1])%d]+=dp[i][j];
    for(int i=0;i<=9;i++) dp[(1<<n)-1][0]/=pre[cnt[i]];
    printf("%lld\n",dp[(1<<n)-1][0]);
}

signed main(){
    pre[0]=1;
    for(int i=1;i<=10;i++) pre[i]=pre[i-1]*i;
    scanf("%d",&T);
    while(T--) solve();
	return 0;
}

P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds

先把问题转化一下，将出现偶数次的奇数偶数之一设为 1，剩下一个设为 0；

那么问题转化为了 01 串操作问题。

不难发现，操作一没有贡献，操作二就是改变 01，最后答案应该是 01 串中的 1 两两就近匹配的之间的距离和。

所以，只有在两个 1 之间的 0 会对答案造成贡献，这个条件等价与这个 0 前面有奇数个 1，

设 0 有 aa 个，1 有 bb 个，枚举每个 0 和 奇数个 1，左右计算组合数，使用乘法原理相乘：

∑i=1a∑i=1b2(i+2j−22j−1)(n−i−2j+1b−2j+1)=∑i=1b2∑i=1a(i+2j−22j−1)(n−i−2j+1b−2j+1)=∑i=1b2(nb+1)=b2(nb+1)\begin{aligned} &\sum^{a}_{i=1} \sum^{\frac{b}{2}}_{i=1} \begin{pmatrix} i+2j-2 \\ 2j-1 \end{pmatrix} \begin{pmatrix} n-i-2j+1 \\ b-2j+1 \end{pmatrix} \\ =&\sum^{\frac{b}{2}}_{i=1} \sum^{a}_{i=1} \begin{pmatrix} i+2j-2 \\ 2j-1 \end{pmatrix} \begin{pmatrix} n-i-2j+1 \\ b-2j+1 \end{pmatrix} \\ =&\sum^{\frac{b}{2}}_{i=1} \begin{pmatrix} n \\ b+1 \end{pmatrix} \\ =&\frac{b}{2} \begin{pmatrix} n \\ b+1 \end{pmatrix} \end{aligned}

在用加法原理加上 1 的贡献 b2(nb)\frac{b}{2} \begin{pmatrix} n \\ b \end{pmatrix} ，

不要忘记奇偶是可以任意排列的，所以再乘上 a!b!a!b!。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e7+5;
int T,mod;
int n;
int pre[N],inv[N];

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

void init(){
    pre[0]=1;
    for(int i=1;i<N;i++) pre[i]=pre[i-1]*i%mod;
    inv[N-1]=qpow(pre[N-1],mod-2);
    for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}

int C(int n,int m){
    return pre[n]*inv[m]%mod*inv[n-m]%mod;
}

void solve(){
    scanf("%lld",&n);
    int a=n/2,b=n-a;
    if(b&1) swap(a,b);
    printf("%lld\n",(((pre[a]*pre[b]%mod)*(b/2%mod)%mod)%mod*(C(n,b+1)+C(n,b))%mod)%mod);
}

signed main(){
    scanf("%lld%lld",&T,&mod);
    init();
    while(T--) solve();
	return 0;
}

P8594 「KDOI-02」一个仇的复

考虑枚举 i,ji,j 分别表示竖着的 1*2 方格的数量和分成的若干矩形的数量。

首先考虑放好 ii 个竖着的 1*2 方格后插空放置 jj 个空矩形，有 (i+1j)\begin{pmatrix} i+1 \\ j \end{pmatrix} 种方案。

其次考虑每一段分多少长度，即 n−in-i 分给 jj，方案数 (n−i−1j−1)\begin{pmatrix} n-i-1 \\ j-1 \end{pmatrix}。

最后考虑每段内的方案数，设第 ll 段分到 ala_l 的长度，需要使用 blb_l 个横着的矩形。

再次考虑插板法，把两行拼接成一行，相当于少了一个空且事先放好一个板子，方案数 (2al−2bl−2)\begin{pmatrix} 2a_l-2 \\ b_l-2 \end{pmatrix}，

考虑所有段放在一起利用乘法原理，得到：

∑∑a=n−i∑b=k−j∏l=1j(2al−2bl−2)=(2(n−i)−2k−j−2)\begin{aligned} &\sum_{\substack{\sum a=n-i \\ \sum b=k-j}} \prod_{l=1}^{j} \begin{pmatrix} 2a_l-2 \\ b_l-2 \end{pmatrix} \\ =&\begin{pmatrix} 2(n-i)-2 \\k-j-2 \end{pmatrix} \end{aligned}

以上三个计算出来的利用乘法原理乘一起就行了，

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e7+5;
const int mod=998244353;
int n,k;
ll ans;
int pre[N],inv[N];

ll qpow(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

void init(){
    pre[0]=1;
    for(int i=1;i<N;i++) pre[i]=(ll)pre[i-1]*i%mod;
    inv[N-1]=qpow(pre[N-1],mod-2);
    for(int i=N-2;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
}

ll C(ll x,ll y){
    if(x<0||y<0||y>x) return 0;
    return (ll)pre[x]*inv[y]%mod*inv[x-y]%mod;
}

signed main(){
    init();
    scanf("%d%d",&n,&k);
    for(int i=0;i<=k;i++) 
        for(int j=0;j<=k;j++) 
            (ans+=(ll)C(2*n-2*i-2*j,k-i-2*j)*(ll)C(n-i-1,j-1)%mod*(ll)C(i+1,j)%mod)%=mod;
    printf("%lld",ans+(n==k));
    return 0;
}