题目描述
我们把一个数称为有趣的，当且仅当：
1.它的数字只包含 0,1,2,3，且这四个数字都出现过至少一次。
2.所有的 0 都出现在所有的 1 之前，而所有的 2 都出现在所有的 3 之前。
3.最高位数字不为 0。
因此，符合我们定义的最小的有趣的数是 2013。
除此以外，4 位的有趣的数还有两个：2031 和 2301。
请计算恰好有 n 位的有趣的数的个数。
由于答案可能非常大，只需要输出答案除以 109+7 的余数。
输入格式
输入只有一行，包括恰好一个正整数 n。
输出格式
输出只有一行，包括恰好 n 位的整数中有趣的数的个数除以 109+7 的余数。
数据范围
4≤n≤1000
输入样例：
4
输出样例：
3
思路(数学解法)
一共要放n位，0,1是有限制的，2,3是有限制的，但是0,1和2,3之间是没有任何限制的，所以我们在放的时候，可以先放0,1再放2,3。先考虑那些未知放0,1，然后剩余的位置放2,3
当0,1的个数不同的时候，方案一定不一样：（因为0,1每个数至少出现一次，所以从2开始枚举）
当0,1有2个的时候，2,3有n-2个
当0,1有3个的时候，2,3有n-3个
当0,1有4个的时候，2,3有n-4个
……
当0,1有n-2个的时候，2,3有2个
我们不妨设0，1共有k位，2,3共有n-k位
因为第3条规定首位不能为0，所以第一个数不能填0，即前两个数不能填0，1（因为第1条规定0必须在1的前面）
所以我们只能在剩下的n-1个位置中取两个位置填上0,1，然后再填2,3
k位的0,1再继续进行分类：
我们设0有t位，1有k-t位
因为0必须在1之前，所以一旦t确定了，整个数就确定了（即前t位一定为0，后k-t位一定为1
所以0,1的所有不同的方案数完全取决于t的不同的选择的数量
0至少要有1位，所以大于等于1,1也至少有1位，所以小于等于k-1，所以k-1≥t≥1,所以t一共有k-1中选法
同理，2,3,一共有n-k位，所以一共有n-k-1种选法
所以计算公式为$\displaystyle\sum_{k=2}^{n-2}C_{n-1}^k(k-1)(n-k-1)$
接下来求一下k到n-1的组合数
用递推的方法来求
$C_a^b$=$C_{a-1}^b$+$C_{a-1}^{b-1}$
这个式子的推导过程：(报名算法基础课的小伙伴可以看一下AcWing 885. 求组合数 I)
比如说我们要这a个球里面选b个球，然后我们随便取一个球数来
然后我们就可以把情况分成两类：一种是选这个球，一种是不选这个球
那么我们总共的方案数之和应该是这两种方案之和
选这个球的话，相当于我们要在剩余的a-1个球里面选b-1个球，即$C_{a-1}^{b-1}$
不选这个球的话，相当于我们要在剩余的a-1个球里选b个球，即$C_{a-1}^b$
所以我们总共的方案数就是$C_a^b$=$C_{a-1}^b$+$C_{a-1}^{b-1}$
代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1010,MOD=1e9+7;
int n;
int c[N][N];
int main()
{
cin>>n;
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])%MOD;
}
}
long long int res=0;
for(int k=2;k<=n-2;k++)
{
//res=(res+(LL)c[n-1][k]*(k-1)%MOD*(n-1-k)%MOD);//如果数据范围比较大的话，用这种写法
res=(res+(LL)c[n-1][k]*(k-1)*(n-1-k))%MOD;//这题的数据范围较小，可以最后取模
}
cout<<res<<endl;
}
