CCF软考---《有趣的数》

脑子一热报了CCF的软测。。但是又觉得好像并没有什么卵用，就当为蓝桥杯预热然后顺便去软件学院玩一玩吧，遇到一个有意思的题：

time limits ： 1s

问题描述

　　我们把一个数称为有趣的，当且仅当：
　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
　　3. 最高位数字不为0。
　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。

输入格式

　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。

输出格式

　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。

样例输入

4

样例输出

3

数位统计问题。。臣妾真的做不到啊。。把网上的两种方法在这里总结一下下。

方法一：数位DP

容易得到（我他妈怎么没想到），每一个n位有趣的数，都是从n-1位的某个数转移过来的（n-1位可能不是有趣的数），那麽可以根据组成数字的元素，把数字分成这这么6种数字：

0：{2}---只含有2，很显然开头有趣的数的第一个数字肯定是2，类似2222；

1：{2,0}

2：{2,1}

3：{2,1,0}

4：{2,1,3}

5：全部4种数字

定义状态d【n】【6】；d【i】【j】表示i位数，状态为j的种类数；

转移很简单，d【i】【0】 = 1（只有2组成）；

d【i】【1】 = (d[i-1][0] + d[i-1][1]*2)%mod;（可以在n-1位只含2的数后面加一位0，或在n-1位含有2，0的数后面加个0或2，以下都可以很轻松地推出，注意0在1前面，2在3前面）

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
",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
",sum);
}

方法三：矩阵，递推。。。待补充