问题描述
| 试题编号： | 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
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 #include<cmath> 10 #include<stack> 11 #include<queue> 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair<string, string> pr; 17 18 int n; 19 const int maxn = 1005; 20 int dp[maxn][10]; 21 const int mod = 1000000007; 22 23 int main() 24 { 25 scanf("%d", &n); 26 for(int i = 1; i <= n; i++){ 27 dp[i][0] = 1; 28 dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod; 29 dp[i][2] = (dp[i - 1][0] + dp[i - 1][2] * 2 % mod) % mod; 30 dp[i][3] = (dp[i - 1][2] + dp[i - 1][3] * 2 %mod) % mod; 31 dp[i][4] = ((dp[i - 1][2] + dp[i - 1][1]) % mod + dp[i - 1][4] * 2 % mod) % mod; 32 dp[i][5] = ((dp[i - 1][3] + dp[i - 1][4]) % mod + dp[i - 1][5] * 2 % mod) % mod; 33 } 34 printf("%d ", dp[n][5]); 35 return 0; 36 }