数

Description

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

(nleq10^{20},mleq100)

Input Format

一行两个整数n，m。

Output Format

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

Sample Input

1 1

Sample Output

解析

大致题意：给定一个位数不超过(20)位的正整数(n)，求(n)的互异排列中有多少种情况恰为(m)的倍数，不能存在前导(0)。

假如(nleq10^{16},mleq20)，那显然可以直接状压(dp)来计数，设(f[S][i])代表(n)中取数情况为(S)，得到的数模(m)余(i)的方案总数，可以枚举一个(j)来转移，时间复杂度(O(2^{lg_n}lg_nm))。

当(nleq10^{20},mleq100)时，空间时间就都不行了。其实，在数字(n)中，很可能有多个一样的数字，而之前的状态我们把每一位数字都当做不一样的来处理，这样既费空间，又还需要额外判断重复状态。所以我们需要一种既能具体唯一表示状态，又不会有重复的状压方法。

对于这题来说，有一种很合适的状压方法：变进制状压。我们把(0-9)每一种数字各用了几次压成一个状态，例如(0)出现了一次，那么在状态中代表的权值就是(1)，同理(2)个(0)代表的权值就是(2)，假设有(cnt_0)个(0)，那么权值就分别是(1-cnt_0)，但是一个(1)代表的权值就是(cnt_0+1)了，一个(1)和一个(0)代表的权值是(cnt_0+2)，两个(1)代表的权值是(2cnt_0+1)，以此类推，这样可以以每一个数出现的次数来不重不漏地表示每一个状态。

显然，当每一个数字出现的次数尽可能平均时，代表的状态权值最大，实际测试可以发现最大权值不超过(60000)，这样利用之前的转移方法就可以通过本题了，时间空间都没有问题。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353 , SIZE = 25 , Maxbit = 12 , M = 120 , MaxS = 60000;
char num[SIZE];
int m,len,cnt[Maxbit],f[MaxS][M];
int base[Maxbit],full[Maxbit],now[Maxbit];
inline void input(void)
{
    scanf("%s",num+1);
    len = strlen( num + 1 );
    scanf("%d",&m);
}
inline void init(void)
{
    for (int i=1;i<=len;i++)
        cnt[ num[i] - '0' ] ++;
    base[0] = 1 , full[0] = cnt[0];
    for (int i=1;i<=9;i++)
    {
        base[i] = full[i-1] + 1;
        full[i] = full[i-1] + base[i] * cnt[i];
    }
}
inline void dp(void)
{
    for (int i=1;i<=9;i++)
        if ( cnt[i] )
            f[base[i]][i%m] = 1;
    for (int S=1;S<=full[9];S++)
    {
        int S_ = S;
        for (int i=9;i>=0;i--)
            if ( cnt[i] )
                now[i] = cnt[i] - (S_/base[i]) , S_ %= base[i];
        for (int i=0;i<=9;i++)
        {
            if ( !now[i] ) continue;
            for (int j=0;j<m;j++)
            {
                int k = ( (j*10) % m + i ) % m;
                f[ S + base[i] ][k] = ( f[ S + base[i] ][k] + f[S][j] ) % Mod;
            }
        }
    }
}
int main(void)
{
    input();
    init();
    dp();
    printf("%d
",f[full[9]][0]);
    return 0;
}

<后记>