組合計數在高中階段是數學的一個必修的章節，難度不大。所以你以為的組合計數題僅僅是像這樣對嗎？

[HNOI2008]越獄

題目描述

監獄有 n個房間，每個房間關押一個犯人，有 m?種宗教，每個犯人會信仰其中一種。如果相鄰房間的犯人的宗教相同，就可能發生越獄，求有多少種狀態可能發生越獄。

答案對 100,003取模。

這個問題很簡單對吧，直接用等價轉換法和乘法計數原理就可做出來了。

但是和數論結合的組合計數才是真正的硬菜：

AcWing 213.古代豬文(SDOI2010)

同樣是省選考察組合計數，為啥過了兩年SD的就比HN的難了這么多呢？

重要引理：Lucas定理：。

這題可以很容易想到以下幾步操作：看到冪的形式，想到歐拉定理的推論，直接將指數對取模就行。然后通過試除法來枚舉n的約數d，然后一個個用Lucas定理求出取模后的值相加得到指數，再用一次快速冪即可。但是由于999911659是質數，=

999911658。這個模數太過于巨大，會導致Lucas定理退化成O(n)的時間復雜度，不能接受。所以接下來就是重頭戲：優化。

1.對于999911658的分析：將這個數分解質因數得到：999911658=2*3*4679*35617。這個分解式有一個很明顯的特點就是：所有因子的次數都是1。在這里考慮到用CRT。

思路就是將2、3、4679、35617分別作為模數求出指數取模后的值分別設為a1，a2，a3，a4，然后求解一個線性同余方程組即可。

這個題目還是主要來考察CRT的運用啊，我們還是要先去想到縮小模數，對于很大的模數進行分解質因數，發現特殊的性質，便想到采用CRT。（對CRT求出的通解的實質理解要深刻）

代碼如下：?

#include<iostream> using namespace std; const int mod=999911658; typedef long long ll; ll a[5],b[5]={0,2,3,4679,35617},fac[500010],ans; void init(ll n){fac[0]=1;for(ll i=1;i<=n;i++){fac[i]=fac[i-1]*i%n;} } ll qmi(ll a,ll k,ll p){ll res=1;while(k){if(k&1) res=res*a%p;a=a*a%p;k>>=1;}return res%p; } ll C(ll n,ll m,ll p){if(n<m) return 0;return fac[n]*qmi(fac[n-m],p-2,p)%p*qmi(fac[m],p-2,p)%p; } ll lucas(ll n,ll m,ll p){if(n<m) return 0;if(!n) return 1;return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p; } void CRT(){for(int i=1;i<=4;i++){ll Mi=mod/b[i];ll t=qmi(Mi,b[i]-2,b[i]);ans=(ans+a[i]*Mi%mod*t%mod)%mod;} } int main(){ll n,q;cin>>n>>q;if(q%(mod+1)==0){cout<<0;return 0;}for(int k=1;k<=4;k++){init(b[k]);for(ll i=1;i*i<=n;i++){if(n%i==0){a[k]=(a[k]+lucas(n,i,b[k]))%b[k];if(i*i!=n){a[k]=(a[k]+lucas(n,n/i,b[k]))%b[k];}}}}CRT();cout<<qmi(q,ans,mod+1); }

AcWing 212.計數交換（史詩級難度）

首先我們先考慮題目中最少的交換次數m要如何求出。一開始我還在想是不是用歸并排序求逆序對的個數，后來才發現我是個**。逆序對的個數表示的其實是：每次交換相鄰的兩個數最后使得序列有序的最少操作次數。而題目中是可以任意交換的。所以這里要來擴展知識了：如何用最少的操作次數使得1-n的一個任意排列變為升序排列？（一次操作指的是交換序列中的任意兩個元素）。我們考慮在p[i]與i之間連一條有向邊，容易知道最后這個序列中會存在若干個環。那么我們的目標就是把這若干個環全部變成自環，并求出其最少的操作次數。

我們猜想：把一個長度為n的環變成n個自環，至少需要(n-1)次操作。

證明：利用數學歸納法，當i=1時，結論顯然成立。那么假設對于任意整數k()，這個結論都成立。那么當k=n時，我們交換這個環中的任意兩個元素vi,vj（i<j）。很顯然兩環的長度分別為j-i與n-(j-i)，總操作次數為j-i-1與n-(j-i)-1，總和為n-2，加上之前的操作次數為n-1次。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 證畢

有了這一步的鋪墊，下面的轉化就更加輕松了。對于上面的證明過程，我們不妨假設將長度為n的環拆成長度分別為x，y的兩個環有T(x，y)種方法。那么容易知道：T(x,y)=n/2(if x==y且n為偶數)，n(else)。

所以將長度為n的環拆成n個自環的方法總數Fn就出來了：……（注意復習：多重集的排列數：見《算法進階指南》P171）

那么最終答案為：……（式子太復雜，可以自己推，推完了看《算法進階指南》P173）

當然，這樣還不能過掉這一道史詩級的難題。因為Fn的復雜求法，使得時間復雜度達到了O(n^2)，但是我們通過找規律發現Fn=n^(n-2)，可以把時間復雜度縮減至O(nlogn)。（等我更新后的證明）

總結：我們在多刷題的同時要多記一些可用的模板，作為自己的知識儲備。（就像學數學一樣，在一道題中接觸到的方法也許在以后的某一道題中也可以得到應用）。

錯排列

錯排列：顧名思義，是指完全錯開的排列：即n個信封所匹配的n個信件全部裝錯的方案總數。那么根據容斥原理，很容易推出下列公式：錯排列公式

那么在這里主要講解一下錯排列的遞推公式：D[n]=(n-1)(D[n-1]+D[n-2])，證明如下：

考慮第k個數排在第n位，一共有n-1種選法。

再考慮第n個數：

如果第n個數排回了第k位，那么無疑n個位置中已經有2個位置已經確定。那么剩下可能的選擇方案數為D[n-2]種。

如果第n個數沒有排回第k位，那么此時的n相當于前面過程中任意的k。選擇的方式相當于是在剩下的n-1個數中再做一次錯排列，方案數為D[n-1]種。

綜上所述，D[n]=(n-1)(D[n-1]+D[n-2])

例題1：AcWing 230.排列計數

這題就是一個錯排列的裸題了，但是要注意邊界情況的特判：

#include<iostream> #include<cstdio> using namespace std; const int N=1e6+5,mod=1e9+7; typedef long long ll; ll fac[N],inv[N],d[N]; ll qmi(ll a,ll b,int p){ll res=1;while(b){if(b&1) res=res*a%p;a=a*a%p;b>>=1;}return res%p; } void init(){fac[0]=1;for(int i=1;i<N;i++){fac[i]=fac[i-1]*i%mod;inv[i]=qmi(fac[i],mod-2,mod);}d[2]=1;for(int i=3;i<N;i++){d[i]=(i-1)*(d[i-1]+d[i-2])%mod;} } int main(){int T;scanf("%d",&T);init();while(T--){ll n,m;scanf("%lld%lld",&n,&m);if(n-m==1) puts("0");else if(n==m) puts("1");else if(!m) printf("%lld\n",d[n]);else{printf("%lld\n",fac[n]*inv[m]%mod*inv[n-m]%mod*d[n-m]%mod);}}return 0; }

范德蒙德卷積

公式如下：

這個公式可以用來化簡式子，減少時間復雜度。

組合計數類題目的其它解題技巧：?

1.動態規劃法

有一些組合計數類題目不易于直接從組合數角度計算，那么不妨從動態規劃的角度入手，找出遞推關系式來解決問題。甚至組合數的預處理方法也是動態規劃法，即：。

所以引出了求組合數方法1：

#include<iostream>//用楊輝三角來理解也是可以的 using namespace std; const int N=2005,mod=1e9+7; int C[N][N]; int main(){int n;cin>>n;for(int i=0;i<N;i++){for(int j=0;j<=i;j++){if(!j) C[i][j]=1;//三角邊界上的1else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}}while(n--){int a,b;cin>>a>>b;cout<<C[a][b]<<endl;}return 0; }

例題1：Bulls and Cows

這題就是一個經典的動態規劃解決計數類問題的題目，本題較易，僅供參考。

2.轉換角度法

組合計數題有時會存在去重遺漏之類的麻煩情況，那么不妨轉換一下看問題的角度，興許就可以解決問題。

例題1：CQOI2014數三角形

這題本人一開始的想法十分復雜，實際上我們可以直接考慮枚舉每一條線段（兩個端點可以直接確定，故枚舉端點即可）。那么我們選三角形時就不妨直接將這兩個端點固定下來，然后在線段上再另找任意一點即可。這樣不用考慮一整條所在直線去重之類的情況，不但簡化了程序，還做到了不重不漏。

#include<iostream> using namespace std; const int N=1e3+5; typedef long long ll; int gcd(int a,int b){if(!b) return a;return gcd(b,a%b); } ll C(int a){return (ll)a*(a-1)*(a-2)/6; } int main(){int n,m;cin>>n>>m;ll res=C((m+1)*(n+1))-(m+1)*C(n+1)-(n+1)*C(m+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int d=gcd(i,j);res-=2ll*(ll)(m-j+1)*(n-i+1)*(d-1);}}cout<<res<<endl; }

總結

以上是生活随笔為你收集整理的关于组合计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。