Description

题目链接

题目大意:多测,求 $s$ 有多少种排列使得其能被 $d$ 整除。$1 \le |s| \le 10, 1 \le d \le 1000, 1 \le T \le 15$。

Solution

约定 $n = |s|$。

设 $f(S, p)$ 为使用了集合 $S$,模 $d$ 为 $p$ 的排列个数,不难发现答案为 $f(2^{n} - 1, 0)$。

考虑转移:$f(S, p) \rightarrow f(S \cup \{x\}, (10p + s_x) \bmod d)$,其中 $x \not \in S$。边界 $f(0, 0) = 1$。

我们发现会有一些漏洞,当有数字重复出现时,我们的程序会认为它们是不同的数字,而实际上它们除了位置不一样以外都相同,因此需要用数组记录该数字有没有用过。

或者最后将答案除以每个数出现的排列数的乘积,这样做也是正确的。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int f[1 << 12][1010];
int a[20];
int T, d, n;
char s[20];
bool vis[20];

int main() {
    read(T);
    while (T--) {
        scanf("%s %d", s + 1, &d);
        n = strlen(s + 1);
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i)    a[i] = s[i] - '0';
        for (int i = 0; i < (1 << n); ++i) {
            memset(vis, false, sizeof(vis));
            for (int j = 1; j <= n; ++j) {
                if ((!(i & (1 << (j - 1)))) && (!vis[a[j]])) {
                    vis[a[j]] = true;
                    for (int k = 0; k < d; ++k) {
                        f[i | (1 << (j - 1))][(k * 10 + a[j]) % d] += f[i][k];
                    }
                }
            }
        }
        printf("%d\n", f[(1 << n) - 1][0]);
    }
    return 0;
}
Last modification:September 2nd, 2021 at 02:03 am