P4163 [SCOI2007]排列

Problem

给一个数字串 \(s\) 和正整数 \(d\), 统计 \(s\) 有多少种不同的排列能被 \(d\) 整除（可以有前导 \(0\)）。
多组数据。

\(\left\vert s\right\vert \le 10，1 \le d \le 1000，1 \le t \le 15\)

Input

第一行一个整数 \(t\)，表示数据组数。
接下来 \(t\) 行，每行一个数字串 \(s\) 和一个整数 \(d\)。

Output

每组数据一行一个整数表示答案。

Sample

Input 1

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

Output 1

1
3
3628800
90
3
6
1398

Solution

观察到 \(\left \vert s \right \vert\) 很小，可以尝试状压。

定义 \(f_{i,j}\) 表示当前选数集合为 \(i\)，形成的数模 \(d\) 与 \(j\) 的方案数。转移方程不难写出：

\(f[i | 1 << k][ (j\times 10 + a_k) \% d ] = f[i | 1 << k][ (j\times 10 + a_k) \% d ] + f[i][j]\)

但直接转移会计算重复，因为 \(s\) 中会有相同的元素。

又因为 \(\left \vert s \right \vert \le 10\)，故每次转移时标记下即可。

代码：

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

using namespace std;

const int kmax = 1e3 + 3;
const int kmaxM = 13;

int a[kmax];
bool b[kmax];
char c[kmax];
int t, n, d;
long long f[1 << kmaxM][kmax];

void Solve() {
  scanf("%s %d", c, &d);
  n = strlen(c);
  for (int i = 0; i < n; i++) {
    a[i] = c[i] - '0'; 
  }
  memset(f, 0, sizeof(f));
  f[0][0] = 1;
  for (int i = 0; i < 1 << n; i++) {
    memset(b, 0, sizeof(b)); // 清空标记
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) continue;
      if (b[a[j]]) continue; // 标记过，不要重复计算
      b[a[j]] = 1; // 添加标记
      for (int k = 0; k < d; k++) {
        f[i | (1 << j)][(k * 10 + a[j]) % d] += f[i][k]; // 转移
      }
    }
  }
  printf("%lld\n", f[(1 << n) - 1][0]);
}

int main() {
  scanf("%d", &t);
  while (t--) { // 多组数据
    Solve();
  }
  return 0;
}