【NOIP模拟赛】数位和乘积

2014年9月13日1,5140

【题目描述】

一个数字的数位和乘积为其各位数字的乘积。求所有的N位数中有多少个数的数位和乘积恰好为K。请注意,这里的N位数是可以有前导零的。比如01,02视为二位数,但是他们的数位和乘积都是0。

【输入格式】

一行两个整数N,K

【输出格式】

一个行一个整数表示结果。

【样例输入】

2 3

【样例输出】

2

【样例输入2】

2 0

【样例输出2】

19

【数据范围】

对于20%:N <= 6。

对于50%:N<=16

存在另外30%:K=0。

对于100%:N <= 50,0 <= K <= 10^9。

题解

若K=0

10^n-9^n高精度

若K!=0

将K分解质因数,如果有2357以外的就无解

如果只有2357就可以dp了f[i][a1][a2][a3][a4] 前i为2357分别用了a1,a2,a3,a4个

然后加个高精度

为了不爆内存可以使用滚动数组或者做01背包