CF401D Roman and Numbers

### 题意： 将n(n<=10^18)的各位数字重新排列（不允许有前导零） 求 可以构造几个mod m等于0的数字 ### 分析： 状态压缩 #### 状态： 设f[s][k]表示对于选择数字组合的s来说，%m等于k的排列数量。 第一维大小：2^18 第二维大小：100 #### 阶段： 对于s的选择的枚举。s直接从1枚举到1<<（cnt+1） 这样到了s（n）时，所有能转移到s(n)的状态都已经处理完毕。不会有后效性。 由于对于1~n的所有排列，可以考虑是从中选择任意的n-1个数的所有排列，再在最末尾选上剩余的一个数。 所以之后的s(n)所能转移到的最优解，都是与s(n)有关系的（都是通过在s(n)末尾接上一个数转移的），所以满足最优子结构性质。 #### 转移： 对于给定的s，它的18位二进制表示中的每一位是0或者是1表示这一位上的数选择或者不选择。 我们将i从0循环到cnt，（cnt=n的位数-1）想要枚举的是s的每一位1，即枚举出来这个s所选的所有的数的位置，也就知道了所选择的数。 再枚举一下余数j，这样，可以写出这样的状态转移方程： f[s][(j x 10+w[i])%m]+=f[s^(1<<i)][j] 意义是：每一位的选择都是通过这一位不选择的剩下状态，再把这一位放在末尾组成状态s转移的。 设之前的数为X,X=km+j; 选择了w[i]之后，X=10km+10j+w[i]; 余数就变成了:(10j+w[i])%m #### 然而有一个缺陷。。。 在于对于有重复数字时，会将一个状态转移从“其实是同一个组合”转移多遍， 举例：n=221 111会从101 转移一次，还会从011转移一次。然而这两个组合其实都是2、1,所以会算重。 所以可以在最后的时候进行多重集合的处理。 也可以每次枚举的时候，判断这一位的值是否之前已经处理过了。 if(vis[w[i]]) continue； 代码： ```cpp #include<bits/stdc++.h> #define ll long long const int maxs=(1<<18)+5; const int maxn=110; using namespace std; int cnt=-1,w[20],m; ll f[maxs][maxn],n; bool vis[10]; int main() { for(cin>>n>>m;n;n/=10) w[++cnt]=n%10; f[0][0]=1; for(int s=1;s<1<<cnt+1;s++) { memset(vis,0,sizeof vis);//注意清空 for(int i=0;i<=cnt;i++) { if(s==(1<<i)&&!w[i]) break;//去掉前导零 if(!(s&(1<<i))||vis[w[i]]) continue;//判断是否选择了这一位，并且跳过已经处理过删去w[i]之后转移的情况。 vis[w[i]]=1;//标记处理过这个数了。 for(int j=0;j<m;j++) f[s][(j*10+w[i])%m]=(f[s][(j*10+w[i])%m]+f[s^(1<<i)][j]); } } cout<<f[(1<<cnt+1)-1][0];//f[11..1][0] return 0; } ```