[SCOI 2007] 排列

扫码查看

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=1072

[算法]

状压DP

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXD 1000
const int MAXS = ; int i,j,k,T,len,d,MASK;
char s[];
long long f[MAXS][MAXD];
long long ans;
long long fac[];
int cnt[]; int main()
{ fac[] = ;
for (i = ; i <= ; i++) fac[i] = fac[i-] * i;
scanf("%d",&T);
while (T--)
{
scanf("%s%d",&s,&d);
len = strlen(s);
MASK = ( << len) - ;
memset(f,,sizeof(f));
memset(cnt,,sizeof(cnt));
for (i = ; i < len; i++) cnt[s[i] - '']++;
f[][] = ;
for (i = ; i <= MASK; i++)
{
for (j = ; j < d; j++)
{
for (k = ; k < len; k++)
{
if ((i & ( << k)) == )
f[i | ( << k)][(j * + s[k] - '') % d] += f[i][j];
}
}
}
ans = f[MASK][];
for (i = ; i < ; i++) ans /= fac[cnt[i]];
printf("%lld\n",ans);
} return ;
}
05-19 05:20
查看更多