Codeforces 401D Roman and Numbers

题目大意

Description

给定一个数 N(N<1018) , 求有多少个经过 N 重组的数是 M(M≤100) 的倍数.

注意: ①重组不能有前导零;　②重组的数相同, 则只能算一个数.

Input

第一行两个数 N , M .

Output

输出满足要求的数的个数.

Sample Input

223 4

Sample Output

题解

状压DP.

\(f[i][j]\)中, \(i\)是状态, 表示原数中哪些位已经被新数占用. 因此, 一个Naive的想法就是对于新数的每一位, 进行一次DP, 时间复杂度: \(2^{18} \times 18 \times 18\), 显然会TLE.

我们注意到, 每当我们进行一次转移, 也就是在新数中填入一位的时候, 状态\(i\)都只会变小, 因此我们从\(2^{18} - 1\)往下直接进行一次DP即可. 时间复杂度: \(2^{18} * 18\), 尚可接受.



#include <cstdio>

#include <cstring>

const int LEN = 18, M = 100;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("CF401D.in", "r", stdin);

    #endif

    static long long pw[LEN];

    pw[0] = 1;

    for(int i = 1; i < LEN; ++ i)

        pw[i] = pw[i - 1] * 10;

    long long n, m;

    scanf("%lld%lld\n", &n, &m);

    int len = 0;

    long long tmp = n;

    static int cnt[10];

    for(; tmp; tmp /= 10, ++ len)

        ++ cnt[tmp % 10];

    static long long fac[10];

    for(int i = 0; i < 10; ++ i)

    {

        fac[i] = 1;

        for(int j = 1; j <= cnt[i]; ++ j)

            fac[i] *= j;

    }

    static long long f[1 << LEN][M];

    memset(f, 0, sizeof(f));

    f[(1 << len) - 1][0] = 1;

    /*

    for(int l = len - 1; ~ l; -- l)

        for(long long i = 0; i < 1 << len; ++ i)

            for(int j = 0; j < m; ++ j)

                if(f[i][j])

                {

                    for(int k = 0; k < len; ++ k)

                    {

                        if(n / pw[k] % 10 == 0 && l == len - 1)

                            continue;

                        if(i >> k & 1)

                            f[i ^ (1 << k)][(j + n / pw[k] % 10 * pw[l]) % m] += f[i][j];

                    }

                    f[i][j] = 0;

                } */

    for(int i = (1 << len) - 1; ~ i; -- i)

    	for(int j = 0; j < len; ++ j)

    		if(i >> j & 1 && (i ^ (1 << len) - 1 || n / pw[j] % 10 % 10))

    			for(int k = 0; k < m; ++ k)

    				f[i ^ (1 << j)][(k * 10 + n / pw[j] % 10) % m] += f[i][k];

    long long ans = f[0][0];

    for(int i = 0; i < 10; ++ i)

        ans /= fac[i];

    printf("%lld\n", ans);

}

巴特西