题解 AT_tdpc_number【数】

· · 题解

Update：加入了取模。

数位 DP 的模板题。

发现本题中前导零对答案没有任何影响，所以不需要考虑前导零的问题。下文中默认个位是最后一位。

先设 f_{i,j} 表示后 i 位中数码和对 d 取模后为 j，且可以自由填数（也就是前面已经有一位满足数码小于 n 的对应位）的方案数。枚举这一位填什么，就有

f_{i,j}=\sum_{k=0}^9f_{i-1,j-k\bmod d}

初始值 f_{0,0}=1。

再设 g_{i,j} 为后 i 位中数码和对 d 取模后为 j 的方案数。还是考虑当前位填什么，就有

g_{i,j}=g_{i-1,j-s_i\bmod d}+\sum_{k=0}^{s_i-1}f_{i-1,j-k\bmod d}

其中 s_i 表示 n 在第 i 位的数。初始值 g_{0,0}=0。可以用记忆化搜索实现。

注意到零不是正整数，所以最后答案要减去一。时间复杂度 O(|n|d)，|n| 表示 n 的位数。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=1e5,Mod=1e9+7;

char ch[Maxn+5]; int n,m;
int g[Maxn+5][105],f[Maxn+5][105];
bool vis[Maxn+5][105];

inline int dfs(int x,int y,int flag)
{
    if(flag) return f[x][y];
    if(vis[x][y]) return g[x][y];
    if(!x) return (!y);
    int res=0,id=ch[x]-'0';
    For(i,0,id)
    {
        if(i<id) res=(res+dfs(x-1,((y-i)%m+m)%m,1))%Mod;
        else res=(res+dfs(x-1,((y-i)%m+m)%m,0))%Mod;
    }
    vis[x][y]=1; return g[x][y]=res;
}

int main()
{
    scanf("%d%s",&m,ch+1),n=strlen(ch+1),f[0][0]=1;
    reverse(ch+1,ch+n+1);
    For(i,1,n) For(j,0,m-1) For(k,0,9)
        f[i][j]=(f[i][j]+f[i-1][((j-k)%m+m)%m])%Mod;
    printf("%d\n",(dfs(n,0,0)-1+Mod)%Mod);
    return 0;
}