一些基本的計數方法

?三大原理： 加法原理、乘法原理、容斥原理

容斥原理：奇數個集合為正，偶數個集合為負

有重復元素的全排列。有k個元素，其中第i個有ni個，求全排列的的個數

（n1+n2+......+nk)!/(n1! n2! ......nk!)

可重復選擇的組合。有n個不同的元素，每個元素可以選多次，一共選K個，有多少 種方法

C(n+k-1,n-1)=C(n+k-1,k)

1.加法原理的應用：

UVA11538鏈接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2533

解題思路:

??????1. 計數問題, 有三種相對擺放方式: 水平, 豎直, 對角線. 根據加法原理即可, 并且沒有交集.

?????????水平和豎直是一樣的, 只要n*m矩形旋轉90度. 所以結果是: n*m*(m-1)+n*m*(n-1);

? ? ? 以水平為例，放白后有nm種，放黑后有（m-1)種

??????2. 對角線復雜些, 先來確定對角線的長度: 1,2,3,...,n-2,n-1,n,n,n,...,n,n,n-1,n-2,...,2,1;

?????????其中n的個數是m-n+1 (其中假設m>n);

?????????結果: 2*(2*∑i*(i-1) + (m-n+1)*n*(n-1))??其中累加的范圍是(1<=i<=n-1); (對角線有兩條，所以要乘以2）

?????????化簡得: 2*n*(n-1)*(3*m-n-1)/3

??????3. 綜上所述: n*m*(n+m-2)+2*n*(n-1)*(3*m-n-1)/3

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() {long long n,m;while(cin>>n>>m){if(n==0&&m==0) break;if(n>m) swap(n,m);cout<<n*m*(m-1)+n*m*(n-1)+2*n*(n-1)*(3*m-n-1)/3<<endl;}return 0; }

2.加法問題的一類變形

UVA11401 鏈接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2396

解題思路，分段法，f [n] 記錄最長的那條邊不超過n的放法數， 假設c[n] 為最長邊為n的放法數 ?f [n] = f [n-1] + c[n] 。 假設最長邊為z，其它為 x,y; 則 ? z-x < y < z 當 ?x=1 時， z-1<y<z ?0 種方案， 當 ?x=2 時， z-2<y<z ?1 種方案， ...................................................... 當 ?x=z-1時， 1<y<z ?z-2種方案 所以總計 (z-1)*(z-2)/2 種方案 但是其中包含了x與y想等的情況，因為 x取值為 [ z/2+1 , z-1 ] 區間內可能 x,y相等，共 (z-1)- (z/2+1)+1=z/2-1 種方案 而且x,y與 y,x認為為兩個，重復計算了，所以除以2 所以 c[n]= [ (z-1)*(z-2)/2 -(z/2-1) ] / 2

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1000000+10; long long f[maxn]; int main() {f[3]=0;for(long long x=4;x<=1000000;x++)f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;int n;while(cin>>n){if(n<3) break;cout<<f[n]<<endl;}return 0; }

轉載于:https://www.cnblogs.com/wolf940509/p/6617111.html

總結

以上是生活随笔為你收集整理的数学问题当中的一些基本计数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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