问题描述
| 试题编号： | 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
|
思路：
dp[dig][state]， 第一维表示当前的位数，第二维表示当前的状态。
状态可以分为六种：
0：出现了2
1：出现了2和3
2：出现了2和0
3：出现了2、0、1
4：出现了2、0、3
5：出现了2、0、1、3
因为每个数至少要出现一次，所以不可能出现状态出现了2和1以及出现了0和3，因为第一个不能是0所以不可能有状态只出现了0
那么第i+1位可以由第i位推出
dp[i+1][0] = 1， i+1位填2
dp[i+1][1] = dp[i][0] + dp[i][1]， 前面全是2第i+1位填2，或是前面是2...3...第i+1填3
dp[i+1][2] = dp[i][0] + dp[i][2] * 2， 前面全是2第i+1位填2，或是前面是2...0...第i+1可以填2或是0
dp[i+1][3] = dp[i][2] + dp[i][3] * 2， 前面是2....0...第i+1填1，或是前面是2...0...1...第i+1可以填1或是3
dp[i+1][4] = dp[i][2] + dp[i][1] + dp[i][4] * 2， 前面是2...0...第i+1填3，或是前面是2...3...第i+1可以填0，或是前面是2...0...3...第i+1可以填0或3
dp[i+1][5] = dp[i][3] + dp[i][4] + dp[i][5] * 2， 前面是2...0...1...第i+1填3， 或是前面是2...0...3...第i+1可以填1， 或是前面是2...0...1...3...第i+1可以填1或3
#include<cstdio>
#include<cstdlib>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue> #define inf 0x7fffffff
using namespace std;
typedef long long LL;
typedef pair<string, string> pr; int n;
const int maxn = ;
int dp[maxn][];
const int mod = ; int main()
{
scanf("%d", &n);
for(int i = ; i <= n; i++){
dp[i][] = ;
dp[i][] = (dp[i - ][] + dp[i - ][]) % mod;
dp[i][] = (dp[i - ][] + dp[i - ][] * % mod) % mod;
dp[i][] = (dp[i - ][] + dp[i - ][] * %mod) % mod;
dp[i][] = ((dp[i - ][] + dp[i - ][]) % mod + dp[i - ][] * % mod) % mod;
dp[i][] = ((dp[i - ][] + dp[i - ][]) % mod + dp[i - ][] * % mod) % mod;
}
printf("%d\n", dp[n][]);
return ;
}