脑子一热报了CCF的软测。。但是又觉得好像并没有什么卵用，就当为蓝桥杯预热然后顺便去软件学院玩一玩吧，遇到一个有意思的题：
time limits ： 1s
d[i][2] = (d[i-1][0] + d[i-1][2])%mod;
d[i][3] = (d[i-1][1] + d[i-1][3]*2 )%mod;
d[i][4] = (d[i-1][2] + d[i-1][1] + d[i-1][4]*2)%mod;
d[i][5] = (d[i-1][3] + d[i-1][4] + d[i-1][5]*2)%mod;
另外注意会爆int
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int mod = 1000000007; int n; ll d[maxn][6]; int main() { for(int i = 1; i <= 1000; ++i) { d[i][0] = 1; d[i][1] = (d[i-1][0] + d[i-1][1]*2)%mod; d[i][2] = (d[i-1][0] + d[i-1][2])%mod; d[i][3] = (d[i-1][1] + d[i-1][3]*2 )%mod; d[i][4] = (d[i-1][2] + d[i-1][1] + d[i-1][4]*2)%mod; d[i][5] = (d[i-1][3] + d[i-1][4] + d[i-1][5]*2)%mod; } scanf("%d",&n); printf("%lld\n",d[n][5]); }
方法二：推公式
能不能不递推，直接o（1）地算出答案呢？当然可以！
已知0，1，2，3都必须出现一次，那么我们可以枚举0，1出现的次数，或者说占用的位数；
0，1加在一起至少出现占2位，最多占n-2位，假设为i位，则首位为2，还剩n-1位，从n-1位里面挑i位分给0，1，有Cn-1，i种方案，然后0，1内部有i-1种排列方式，2，3内部有
n-i-1种反案，所以最后答案：
然而这种方法要o（n^2）利用杨辉三角预处理组合数，最后时间和第一种方法跑起来差不多。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int mod = 1000000007; int n; ll c[maxn][maxn]; ll sum; int main() { for(int i = 0; i <= 1000; ++i) { c[i][0] = 1; for(int j = 1; j < i; ++j) { c[i][j] = (c[i-1][j-1] + c[i-1][j])%mod; } c[i][i] = 1; } scanf("%d",&n); for(int i = 2; i <= n-2; ++i) { sum = (sum + c[n-1][i]%mod*(i-1)*(n-i-1))%mod; } printf("%lld\n",sum); }
方法三：矩阵，递推。。。待补充
原文：http://www.cnblogs.com/Norlan/p/5011059.html