3195. 有趣的数-13年12月CCF计算机软件能力认证（组合数）

题目

思路

1. 统计方案的时候先去分类，先放01，然后在考虑23
   
2. 对于第k类，
   
   对于01的选择
   
   对于所有的分类：
   
3. 
4. 本题我觉得要考虑的几个点就是：状态分类得到数学公式+组合数的计算+防越界处理

代码

计算组合数的代码模板：

for (int i = 0; i < n; ++i) {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]);}
}
C[n][m];

AC代码：

# include<bits/stdc++.h>
using namespace std;
const int N=1010;
int m=1e9+7;
int main(){int n;cin>>n;long long c[N][N]; //防止越界for(int i=0;i<=n;i++){ //组合数从0~nfor(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])%m; //要取余，否则会越界}}}long long ans=0; //防止越界for(int k=2;k<=n-2;k++){ans =(ans+ c[n-1][k]*(k-1)*(n-k-1))%m;}// ans=ans%m;cout<<ans<<endl;return 0;
}