智灵班第三次模拟考T2:幸运数字题解

常规
1

接下来的区域符号%统一使用 M 代替(因为%打不出来QAQ)

T2:幸运数字:

题目描述
小y是一个非常喜欢数码的同学，小z是一个特别喜欢取余操作的同学，有一天他们决定一起玩一个游戏来决定谁更加幸运。

小y说我决定幸运的数字它的数码中不应该含有 0，并且它的数码和应该等于y.

例如 y =4 的时候，112、4、22 等的数码和为 4，对于小y来说就是幸运数字，但是 40 虽然数码和为 4，但是含有 0 就不是 小y 的幸运数字

小z说我决定幸运数字应该是对 z 取余等于 0 的。 例如 z =2 的时候 2 的倍数 0，2，4，6，8 等就是小 z 的幸运数字。

于是他们叫来了他们的数学老师Kumb，希望他能够统计出同时满足他们两个人条件的幸运数字有多少。

幸运数的个数可能很大，请你对 1000000007取模

Input:

第一行 两个数一个 y一个 z

Output:

输出一行，含有一个整数 输出同时满足两个条件的幸运数的个数。

样例:

4 2
3

思路:

先从题面开始分析。此题给了2个限制条件。第一是数码和为 y ,第二是可以被 z 整除。
从数学方面想发现并没有什么很好的做法.又根据数据量可以得出 考虑动态规划.

第一步:定义状态

给出了2个限制条件那么就需要使用二维数组来完成.
设 dp[i][j] 为数码和为 i , 对 z 取余为 j 的数的个数.

第二步:确定遍历方向

这里的动态规划思路是: 在原有的数x之后添上一位,得到一个新数 x' 使用 x 和 x' 进行转移.可得出第一重循环是 1~y (因为数码和为y时最大的数也是y位).第二重循环为余数的枚举,从 1~z 第三重循环则是枚举要加哪个数，从 1~9 即可.

第三步:状态转移方程:

设三重循环的下标分别为 i,j,k .一维数码和很简单. dp[i+k][*] 可以由 dp[i] 转移. 第二维则需要判断余数.特殊的，余数时有可能归零.则 dp[*][(10j+k)Mz] 可以由 dp[i] 转移. 得到了状态转移方程 dp[i+k][(10j+k)Mz]+=dp[i][j].

第四步:输出

想要数码和是 y ,取余 z 为0. 输出的就是 dp[y][0]

时间复杂度分析:

线性时间复杂度,实际复杂度 O(9yz). 近似 O(yz)

Code:

for(/*从1-y*/){
    for(/*从1-z*/){
        for(/*从1-9*/){
            状态转移方程
        }
    }
}
cout<<dp[y][0];
1 个赞