这个动规实际上是数位dp当中的简单题。

问题的分析下面那位大佬已经讲的很清楚了，见下一篇题解。

注意：const int p=100000007而不是1e9，否则返回的值是浮点数和答案不符！

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define in inline
#define rint register int
typedef long long int LL;
typedef pair<int,int> PII;

in int read()
{
    rint x=0,f=0; register char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}

/*----------code----------*/
const int N=1010,p=100000007;
int f[N][N*10];

LL qmi(LL a,int k) //快速幂求a^k 
{
    LL res=1;
    for(;k;k>>=1)
    {
        if(k&1) res=res*a%p;
        a=a*a%p;
    }
    //cout<<res<<endl;
    return res;
}

int main()
{
    memset(f,0,sizeof f);
    int n,k; n=read(),k=read();
    
    for(int i=1;i<=9;i++) f[1][i]=1;
    
    for(rint i=2;i<=n;i++) //枚举位数
        for(rint j=1;j<=k;j++) //枚举上一次数位之积的大小
            for(rint u=1;u*j<=k&&u<=9;u++) //枚举这一位是多少
                f[i][j*u]=(f[i][j*u]+f[i-1][j])%p;
    
    //公式：首位的选择数*(后面所有位数的所有选择数-没有0的选择数)
    LL res=9*(qmi(10,n-1)-qmi(9,n-1)); //计算至少有一个零的情况(只要有零，数位之积就为0)
    for(int i=1;i<=k;i++) res=(res+f[n][i])%p;
    cout<<res;
    
    return 0;
}

暴力方法就不说了，用for循环每次判断积有没有超过k，大家都会。
正解是动态规划。
我们先不考虑0的问题，设dp[n][k]是n位不含0的数，数位之积为k的数量，则
dp[n][k] = \(\sum_{ij=k,0<j<10}\) dp[n-1][i]

(第1位放j，其余按照dp[n-1][i]的方案。注意必须限定0<j<10)

如果后\(n-1\)位含有\(0\)(一共有\(10^{n-1}\)个数中，减去不包含\(0\)的\(9^{n-1}\)个数，剩下的数都是含有\(0\)的)
且第一位可以取1~9的任意数，所以答案\(9*(10^{n-1}-9^{n-1})\)

所以只要将两部分加起来就行。时间复杂度\(O(nk)\)

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const ll mod = 100000007;
ll powmod(ll a,ll b){ll res=1;a%=mod; assert(b>=0);for(;b;b>>=1){if(b&1) res=res*a%mod;a=a*a%mod;}return res;}

int dp[1005][10005];
int main()
{
    int n,k;cin>>n>>k;
    for(int i=1; i<=9; i++) dp[1][i] = 1;
     
    for(int i=2; i<=n; i++) 
        for(int j=1; j<=k; j++)
            for(int p = 1; p*j<=k&&p<10; p++)
                dp[i][j*p] += dp[i-1][j], dp[i][j*p] %= mod;    
    
    ll ans = 9* (powmod(10,n-1) - powmod(9,n-1));
    for(int i=1; i<=k; i++) ans+=dp[n][i];
    cout<<ans%mod;
    
    return 0;
}