[SCOI2007]排列（状压DP）

题目

题目描述

给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能

被2整除，其中末位为2的有30种，末位为4的有60种。

题解

• f [ S ] [ i ] f[S][i] f[S][i]表示当前选的数的集合为 S S S，对 d d d取余的余数为 i i i
• 考虑转移设新加的数的位置为 x x x那么 f [ S   o r   x ] [ ( i ∗ 10 + a [ x ] )   m o d   d ] + = f [ S ] [ i ] f[S \ or \ x][(i*10+a[x])\bmod d] +=f[S][i] f[S or x][(i∗10+a[x])modd]+=f[S][i]
• 算答案时除去重复即可

code

#include <bits/stdc++.h> 

using namespace std; 

const int N = (1 << 10) + 100; 
const int M = 1e3 + 10; 
const int Z = 10; 

int T, n, d; 
char ch[N]; 
int cnt[Z], fac[Z]; 
int f[N][M]; 

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%s %d", ch + 1, &d); 
		n = strlen(ch + 1); 
		for (int i = 0; i <= 9; ++i) cnt[i] = 0, fac[i] = 1; 
		for (int i = 1; i <= n; ++i) cnt[(int)(ch[i]-'0')]++; 
		for (int i = 0; i <= 9; ++i) 
			for (int j = 1; j <= cnt[i]; ++j) 
				fac[i] *= j; 

		memset(f, 0, sizeof(f)); 
		f[0][0] = 1; 

		for (int s = 0; s < (1 << n); ++s) {
			for (int j = 0; j < d; ++j) {
				for (int i = 1; i <= n; ++i) {
					if (s & (1<<(i-1))) continue; 
					f[s|(1<<(i-1))][(10*j+(int)(ch[i]-'0'))%d] += f[s][j]; 
				}
			}
		}

		int ans = f[(1<<n)-1][0]; 
		for (int i = 0; i <= 9; ++i) ans /= fac[i]; 

		printf("%d\n", ans); 
	}
	return 0; 
}