CCF 2013 12-4 Interesting numbers

9/5/2021 5:03:56 PM

subject

Problem description

We call a number interesting , If and only if ：
　　1. Its numbers only contain 0, 1, 2, 3, And all four numbers have appeared at least once .
　　2. be-all 0 All over the world 1 Before , And all 2 All over the world 3 Before .
　　3. The highest number is not 0.
　　 therefore , The smallest interesting number that fits our definition is 2013. in addition to ,4 There are two more interesting numbers ：2031 and 2301.
　　 Please calculate that there happens to be n The number of interesting numbers of bits . Because the answer can be very big , Just output the answer divided by 1000000007 The remainder of .

Input format

There is only one line of input , Including exactly one positive integer n (4 ≤ n ≤ 1000).

Output format

There is only one line of output , Including just n The number of interesting integers divided by 1000000007 The remainder of .

The sample input

4

Sample output

3

Answer key :

Key Word : digit DP、 Status determination

    #include<bits/stdc++.h>
	using namespace std;
	#define LL long long

	const int MOD = 1000000007;
	LL dp[1010][8]; //dp[i][j] It means the first one i Bit compliance status j The number of legal numbers 

	/* 0  It only includes 2 1  It only includes 2、0 2  It only includes 2、3 3  It only includes 2、0、1 4  It only includes 2、0、3 5  contain 4 Kind of number  */ 


	int main()
	{
    
    int n; cin>>n;

    for(int i=1;i<=n;i++){
    
        dp[i][0] = 1;// The first must be  2  Or say   Add 2  Must be satisfied with 

        // It only includes 2 0  It can be  2  Then add 0  But  2 0  Add casually  2 perhaps 0
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]*2 ) % MOD;

        // It only includes 2、3 2 +3  perhaps  23 + 3
        dp[i][2] = (dp[i-1][0] + dp[i-1][2] ) % MOD;

        // It only includes 2、0、1: 2 0 +1 2 0 1 + 1 2
        dp[i][3] = (dp[i-1][1] + dp[i-1][3]*2) % MOD;

        dp[i][4] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][4]*2) % MOD;
		dp[i][5] = (dp[i-1][3] + dp[i-1][4] + dp[i-1][5]*2) % MOD;
    }
    
    cout<<dp[n][5];

    return 0;
	}

understand ：
DP First you have to see : Then this can actually enumerate states Then write the state transition equation
The final result is OK
And a little bit more
Multiple states Not all meet the requirements As long as we can transfer the qualified Then take that number ！
DP[i][j] The first i position The first j States ！

---