【数位DP】JZOJ 5831. 【NOIP提高A组模拟2018.8.18】 number

JZOJ 5831. 【NOIP提高A组模拟2018.8.18】 number

题目

Description

给定正整数 n,m，问有多少个正整数满足：
1、不含前导 0；
2、是 m 的倍数；
3、可以通过重排列各个数位得到 n。

Input

一行两个整数 n，m。

Sample Input

1 1

Output

一行一个整数表示答案对 998244353 取模的结果。

Sample Output

1

Data Constraint

对于 20%的数据，n<10^10。
对于 50%的数据，n<10^16，m<=20。
对于 100%的数据，n<10^20，m<=100。

题解

看看题目，第3个条件很好地说明了这道题目的算法—数位DP。
既然如此，我们想想如何设做，状态怎么设，需要维护哪些条件。不妨对每个条件来做出一定处理。
条件1：DP第1位时从1至9，而其他的是从0至9即可；
条件2：设一维状态表示对于m取余的结果；
条件3：将每个数选择的个数的状态压缩成一个数来维护。
于是，我们设f[i][s][j]$f[i][s][j]$表示第i$i$位，选数的状态为s$s$，对于m取余的结果为j$j$的方案数。
状态转移方程如下：
f[i+1][s′][[(j∗10+k)modm]=(f[i+1][s′][(j∗10+k)modm]+f[i][s][j])$f[i+1][s^{\prime }][[(j\ast 10+k)\mathrm{mod}m]=(f[i+1][s^{\prime }][(j\ast 10+k)\mathrm{mod}m]+f[i][s][j])$
其中，k$k$为每次枚举当前加入的数字，s′$s^{\prime }$为在s$s$的基础上添加k$k$压缩后在状态，注意时刻要保证当前k$k$的个数不能大于n$n$中k$k$的个数。
最后的答案则为f[len][S][0]$f[len][S][0]$，其中len$len$为n$n$的数字位数，S$S$为n$n$中数字出现的状态。
因为时间过大，维护q[i][s]=0/1$q[i][s]=0/1$表示f[i][s][0 m−1]$f[i][s][0m-1]$中是否至少有一位有值，因为我们记录的是方案数，所以如果都是0$0$时就可以跳过了。每次更新f[i+1][s′][[(j∗10+k)modm]$f[i+1][s^{\prime }][[(j\ast 10+k)\mathrm{mod}m]$时把q[i+1][s′]=1$q[i+1][s^{\prime }]=1$即可。
同时，由于空间过大，要使用滚动DP。

代码

#include<cstdio> 
#include<cstring>
using namespace std;
int a[15],b[15],g[15],p[60010][110],q[21][60010];
long long f[2][60010][110];
char z[21];
int main()
{
    int m,i,j,k,l,s;
    scanf("%s",z+1);
    scanf("%d",&m);
    int n=strlen(z+1);
    for(i=1;i<=n;i++) a[z[i]-'0']++;
    g[10]=1;
    for(i=9;i>=0;i--) g[i]=g[i+1]*(a[i]+1);
    memset(f,0,sizeof(f));
    for(i=1;i<=9;i++) if(a[i]) f[1][g[i+1]][i%m]=1,q[1][g[i+1]]=1;
    for(i=1;i<n;i++)
    {
        for(j=0;j<g[0];j++) if(q[i][j])
        {
            int t=j;
            for(k=0;k<=9;k++)
            {
                b[k]=t/g[k+1];
                t%=g[k+1];
            }
            for(k=0;k<=9;k++)
            {
                if(b[k]==a[k]) continue;
                b[k]++;s=0;
                for(l=0;l<=9;l++) s+=b[l]*g[l+1];
                for(l=0;l<m;l++) if(f[i%2][j][l])
                {
                    if(p[s][(l*10+k)%m]!=i+1) 
                    {
                        p[s][(l*10+k)%m]=i+1;
                        f[1-i%2][s][(l*10+k)%m]=f[i%2][j][l];
                        q[i+1][s]=1;
                    }
                    else f[1-i%2][s][(l*10+k)%m]+=f[i%2][j][l];
                    f[1-i%2][s][(l*10+k)%m]%=998244353;
                }
                b[k]--;
            }
        }
    }
    printf("%lld",f[n%2][g[0]-1][0]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}