Problem Specification Value
Time Limit 10 Sec
Memory Limit 128 MB
Submit 1585
Solved 1004

Description

给一个数字串 s 和正整数 d, 统计 s 有多少种不同的排列能被 d 整除 (可以有前导 0). 例如 123434 有 90 种排列能被 2 整除, 其中末位为 2 的有 30 种, 末位为 4 的有 60 种.

Input

输入第一行是一个整数 T, 表示测试数据的个数, 以下每行一组 s 和 d, 中间用空格隔开. s 保证只包含数字 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Output

每个数据仅一行, 表示能被 d 整除的排列的个数.

Sample Input

7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29

Sample Output

1
3
3628800
90
3
6
1398

HINT

在前三个例子中, 排列分别有 1, 3, 3628800 种, 它们都是 1 的倍数.

【限制】

100% 的数据满足: s 的长度不超过 10, 1<=d<=1000, 1<=T<=15

Source

按照每一位的数值来考虑接下来位数整除 d 的值, 也就是数位 DP.


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 1010, maxm = 1025;

int cases, n, d, dp[maxm][maxn];
char str[30];

#define states(x) (1<<(x))

// dp[i][j] = modulo j @ state i.
void dp_work(void)
{
    // Similar to a memset().
    for (int i = 0; i < states(n); i++)
        for (int j = 0; j < d; j++)
            dp[i][j] = 0;
    // Putting nothing here has 1 choice.
    dp[0][0] = 1;
    // Iterate through all states by i.
    for (int i = 0; i < states(n); i++)
        // Iterate through all possible modulus by j.
        for (int j = 0; j < d; j++)
            // That is, at this state i we have some occurences. Now dispatch
            // the data to children.
            if (dp[i][j] > 0)
                // Now we iterate through all digits with x.
                for (int x = 1; x <= n; x++)
                    // If the current digit was not selected, then...
                    if (((1 << (x - 1)) & i) == 0)
                        // printf("dp @ %d %d %d -> %d\n", i, j, x, i & (1 << (x - 1)));
                        // The updated state.
                        dp[i | (1 << (x - 1))]
                        // The new modulo, we multiply 10 because a base-10
                        // digit was shifted forward.
                        [(str[x] + j * 10) % d]
                        // Update with addition of the current state.
                        += dp[i][j];
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &cases);
    for (int idx = 1; idx <= cases; idx++) {
        scanf("%s%d", str + 1, &d);
        n = strlen(str + 1);
        int tot[10], perm[10];
        for (int i = 0; i < 10; i++) {
            tot[i] = 0;
            perm[i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            // Convert into real numbers
            str[i] -= '0';
            // Deduct permutation duplication ( / P_n^n i.e. n! )
            tot[str[i]]++;
            perm[str[i]] *= tot[str[i]];
        }
        // Dynamically programming.
        dp_work();
        for (int i = 0; i < 10; i++)
            dp[(1 << n) - 1][0] /= perm[i];
        // Get result
        int res = dp[(1 << n) - 1][0];
        printf("%d\n", res);
    }
    return 0;
}
from pydatagen import *
T = randrange(10, 15)
printf('%d\n', T)
for i in range(0, T):
    d = randrange(100, 1000)
    n = randrange(1, 10)
    s = ''
    for j in range(0, n):
        s += str(randrange(0, 10))
    printf('%s %d\n', s, d)