| 试题编号： | 201312-4 |
|---|---|
| 试题名称： | 有趣的数 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
我们把一个数称为有趣的，当且仅当： 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 |
思路：
我们从数的第一位开始往后考虑数的每一位，在此过程中，这个数一共会出现六种情况：
| 0 | 全都是2 |
|---|---|
| 1 | 同时有2和0 |
| 2 | 同时有2和3 |
| 3 | 同时有0、2和3 |
| 4 | 同时有0、1和2 |
| 5 | 0、1、2、3同时都有 |
而我们可以得到以上数组的递推关系：
| 递推关系： | cnt [ i ][ 0 ] = 1 |
|---|---|
| 解释： | 全为2的情况永远只有一种 |
| 递推关系： | cnt [ i ][ 1 ] = 1 + cnt [ i - 1 ][ 1 ] * 2 |
| 解释： | 第0种情况再加个0；第1种情况加0或2 |
| 递推关系： | cnt [ i ][ 2 ] = 1 + cnt [ i - 1 ][ 2 ] |
| 解释： | 第0种情况加个3；第2种情况加上3 |
| 递推关系： | cnt [ i ][ 3 ] = cnt [ i - 1 ][ 1 ] + cnt [ i - 1 ][ 2 ] + cnt [ i - 1 ][ 3 ] * 2 |
| 解释： | 第一种情况加上3；第二种情况加上0；第三种情况加上0或3 |
| 递推关系： | cnt [ i ][ 4 ] = cnt [ i - 1 ][ 1 ] + cnt[ i - 1 ][ 4 ] * 2 |
| 解释： | 第一种情况加上1；第四种情况加上1或2 |
| 递推关系： | cnt [ i ][ 5 ] = cnt [ i - 1 ][ 3 ] + cnt [ i - 1 ][ 4 ] + cnt [ i - 1 ][ 5 ] * 2 |
| 解释： | 第三种情况加上1；第四种情况加上3；第五种情况加上1或3 |
数组类型开long long，每次相加完记得取余
最后输出遍历到第n位时的第五种情况，即cnt[n][5]即可~
代码：
#include<iostream>
using namespace std;
#define mod 1000000007
long long int cnt[1001][6];
int main(){
int n;
scanf("%d",&n);
cnt[1][0]=1;
for(int i=2;i<=n;i++){
cnt[i][1]=(1+cnt[i-1][1]*2)%mod;
cnt[i][2]=(1+cnt[i-1][2])%mod;
cnt[i][3]=(cnt[i-1][1]+cnt[i-1][2]+cnt[i-1][3]*2)%mod;
cnt[i][4]=(cnt[i-1][1]+cnt[i-1][4]*2)%mod;
cnt[i][5]=(cnt[i-1][3]+cnt[i-1][4]+cnt[i-1][5]*2)%mod;
}
printf("%lld",cnt[n][5]);
return 0;
}