题意：

将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；

代码：

#include
     
      #define ll long longconst 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<