简要题意：给定n，m，n (1 ≤ n < 10ˆ18) and m (1 ≤ m ≤ 100).求满足以下要求的数x有多少个。

  • x可通过重排n的各位数字获得
  • x没有前导0
  • x mod m == 0

一开始我被10ˆ18给吓到了，但是其实这里也是一个突破口来着，仔细想想，如果是2ˆ18的话那该多好。
如果你往这个方向开始去想了，就会发现很多东西了，然后就是个DP，然后再去一下重，当然，你也可以在DP的过程中去重。
不过，感觉我的DP水平实在是不济，这个是赛后搞出来的。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

const int MN = (1 << 18) + 3;

long long f[MN][103];
int dig[20] = {0};
char c[20];
long long fac[20];
unsigned long l;
int m;

int main(int argc, const char * argv[])
{
    cin >> c >> m;
    l = strlen(c);
    for (int i = 0; i < l; i++) {
        dig[c[i] - '0']++;
    }
    fac[0] = 1;
    for (int i = 1; i < 20; i++) {
        fac[i] = fac[i - 1] * i;
    }
    f[0][0] = 1;
    for (int s = 0; s < (1 << l); s++) {
        for (int j = 0; j < m; j++) {
            if (f[s][j]) {
                for (int i = 0; i < l; i++) {
                    if (~s & (1 << i)) {
                        if (!s && c[i] == '0') {
                            continue;
                        }
                        f[s | (1 << i)][(j * 10 + c[i] - '0') % m] += f[s][j];
                    }
                }
            }
        }
    }
    long long ans = f[(1 << l) - 1][0];
    for (int i = 0; i < 10; i++) {
        ans /= fac[dig[i]];
    }
    cout << ans << endl;
    return 0;
}