题目描述
求一种数的方案数
要求
- 数字只能存在0,1,2,3。且至少出现一次
- 所有的0都在1的前面,所有的2都在3的前面
- (最高位)第一位不能为0
题目分析
$ \ $
如何求$C^{k}_{n - 1}$?
可以使用组合计数的方式
for(int i = 0; i <= n; i ++ )
for(int j = 0; j <= i; j ++ )
if(!j) f[i][j] = 1;
else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]);
$Code$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
typedef long long LL;
int f[N][N];
int n;
int main()
{
cin >> n;
for(int i = 0; i <= n; i ++ )
for(int j = 0; j <= i; j ++ )
if(!j) f[i][j] = 1;
else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
LL ans = 0;
for(int k = 2; k <= n - 2; k ++ )
ans = (ans + ((LL)f[n - 1][k] * (k - 1) % MOD * (n - k - 1)) % MOD) % MOD;
cout << ans << endl;
return 0;
}