2023-07-25 20:41:07 solution
思路
看到这个数据和范围，果断数位 dp。
因为同一个数字交换顺序是一样的，所以我们直接把它们合并即可。
设计状态，观察到每个数字的个数不一定相同，今天集训的时候学到了一个小技巧，
对于一个哈密顿回路（每个点恰好经过一次），我们可以用二进制表示其状态。
那对于一个广义哈密顿回路（好像没有这个概念，我自己编的），每个点恰好经过 \(a_i\) 次。
通常来说，状压是指的二进制状压，因为二进制状压可以方便进行 and,or,xor 等位运算。但是也会有像本题这样非二进制的情况，有些甚至要爆搜出所有情况进行 dp。
但是其实是和二进制同样的状态压缩方式，只是把每个位进位的阈值改了，参考了一下上面巨佬的题解，就叫它变进制数吧。
对于一个二进制数 \(x\)，我们可以将它表示为：
\(x=x_0\times 2^0+x_1\times 2^1+...+x_n\times 2^{n-1}\)。
那么设 \(n\) 中各个数字出现的次数分别为 \(A[i]\)，那么可以把第 \(i\) 为看为一个 \(A[i]+1\) 进制数。
那么我们可以将状态压缩为 \(s\)，则：
\(s=x_0\times 1+x_1\times (A[0]+1)+x_2\times (A[0]+1)\times(A[1]+1)+...\)。
然后就可以状态压缩加数位 dp 了。
\(Code1\)
int A[10],m,p[12];
ll n,f[100][60004];
ll dfs(int zt,int mv){
if(!zt)return !mv;//没数了就返回
if(~f[mv][zt])return f[mv][zt];
ll ans=0;
for(int i=9;~i;--i){//从大到小枚举数
if(zt==p[10]-1&&!i)continue;//首位不能为0
if(zt%p[i+1]<p[i])continue;//去掉前面的位判断是否还有数
ans+=dfs(zt-p[i],(mv*10+i)%m);//转移
}
return f[mv][zt]=ans;
}
int main(){
cin>>n>>m;
memset(f,-1,sizeof(f));
while(n){
A[n%10]++;
n/=10;
}
p[0]=1;
for(int i=1;i<=10;i++){
p[i]=p[i-1]*(A[i-1]+1);//前缀积预处理
}
cout<<dfs(p[10]-1,0);//p[10]-1是一开始状态
}
相似题 P4163 排列
只需要把去前导 \(0\) 的步骤删除，然后加点细节即可。
\(Code2\)
int A[10],m,p[12],T;
int f[1000][1<<10];
int dfs(int zt,int mv){
if(!zt)return !mv;
if(~f[mv][zt])return f[mv][zt];
int ans=0;
for(int i=9;~i;--i){
if(zt%p[i+1]<p[i])continue;
ans+=dfs(zt-p[i],(mv*10+i)%m);
}
return f[mv][zt]=ans;
}
int main(){
scanf("%d",&T);
while(T--){
string n;
cin>>n;
scanf("%d",&m);
memset(f,-1,sizeof(f));
memset(A,0,sizeof(A));
for(int i=0;i<n.length();i++){
A[n[i]^48]++;
}
p[0]=1;
for(int i=1;i<=10;i++){
p[i]=p[i-1]*(A[i-1]+1);
}
printf("%d\n",dfs(p[10]-1,0));
}
}