CSP_20131204有趣的數題解（組合計數）

題目描述：

思路（組合計數問題）

• 根據問題描述，首先把0 1 2 3 分為0 1和2 3兩組
• 對這兩組分别來看，去選擇位置，因為一共有n個位置第一位不能為0，是以0和1這一組隻能選擇2到n這n-1個位置，假設有k個0和1，（k的範圍是2到n-2）那麼有n-k個2和3。是以位置選擇上C(n-1,k) 0 1 選擇好位置之後，所有資料的先後順序就确定了。
• 此時看k個0 1這種情況中資料配置設定情況，可能有1~k-1個0，是以有k-1中情況，同理，n-k個2 3中有n-k-1中情況，是以。k個0 1 中所有情況為C(n-1,k)*（k-1）%mod*(n-k-1)%mod
• k=2到n-2進行周遊即可

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int mod=1e9+7;
int n;
long long int C[N][N];
long long res=0;
int main()
{
	cin>>n;
	for(int i=0;i<=n;i++) //先計算C(i,j) 表示從i個數中選擇j個數的情況 
		for(int j=0;j<=i;j++) 
		{
			if(!j) C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; //記得取mod 
		}
	for(int k=2;k<=n-2;k++)
	{
		res=(res+C[n-1][k]*(k-1)%mod*(n-k-1))%mod;//記得中途取mod不然爆long long 
	}
	cout<<res<<endl;
	return 0;
}