网站图片缩略图,怎么做网站手机版,注册安全工程师报考时间2023,部队网站源码题干#xff1a;
试题编号#xff1a;201312-4试题名称#xff1a;有趣的数时间限制#xff1a;1.0s内存限制#xff1a;256.0MB问题描述#xff1a; 问题描述 我们把一个数称为有趣的#xff0c;当且仅当#xff1a; 1. 它的数字只包含0, 1, 2, 3#xff0c…题干
试题编号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 解题报告 首先2^4-1枚举出所有的可能状态然后分别进行转移。dp[i][j]代表当前有i位已经使用过的数字对应状态为j时的合法方案数。
注意对于这一思路有两种解决一个是转移i-1到i这一位的时候是在后面添加数字另一种是在前面添加数字。对于这一题而言显然前者比较简单因为通过题目可以分析得到最后形成的这个数字的最高位一定是2所以从前往后增加位数的时候就会少讨论很多情况16个状态不需要全部列举出来。但是如果从后往前的话也是可以先看dp[i][15]需要哪些状态再去对那些状态进行转移但是有个问题就是最后得到的答案可能含有前导零所以我们需要先处理到dp[n-1]然后再自行累加到ans中其实也是因为第一位必须是2这个条件。 注意状态的定义比如是dp[i][3]也就代表必须含有2和3而只含有2或者只含有3的方案数 就不应该被统计在内了。也就是说这个状态不能由dp[i-1][2]再末尾添加一个2构成一个方案数而是只能添加一个3因为要保证必须含有2和3所以这里不用乘2。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
ll dp[1055][16];
int main()
{int n;cinn;dp[1][2] 1;for(int i 2; in; i) {dp[i][15] (dp[i-1][11]dp[i-1][14]2*dp[i-1][15])%mod;dp[i][11] (dp[i-1][10]dp[i-1][3]2*dp[i-1][11])%mod;dp[i][14] (dp[i-1][12]dp[i-1][10]2*dp[i-1][14])%mod;dp[i][10] (dp[i-1][2] 2*dp[i-1][10])%mod;dp[i][12] (dp[i-1][12]2*dp[i-1][8]dp[i-1][4])%mod;dp[i][3] (dp[i-1][2]dp[i-1][3])%mod;dp[i][2] dp[i-1][2];}printf(%lld\n,dp[n][15]);return 0 ;}
