D. Roman and Numbers(狀壓dp+前導零)

https://codeforces.com/problemset/problem/401/D

思路：看到這個18開始往數位dp搞了。但是是個狀壓。

定義dp[s][j]：目前取數狀态為s，且modm=j的方案數。

對于排列，我們考慮其枚舉s中的一個數，然後從之前狀态轉移，且枚舉到的這個數放在最後一個位置加進去。這樣第二部分的mod就可以順推，前一個狀态為k，現在加入某個數的狀态可以算出。

之前的數為X,X=km+j;選擇了w[i]之後，X=10km+10j+w[i]; 餘數就變成了:(10j+w[i])%m。

但是這樣會重複轉移。

舉例：n=221 111會從101 轉移一次，還會從011轉移一次。然而這兩個組合其實都是2、1,是以會算重。

是以我們對這次狀态轉移，對于取過的數放最後一位進行标記不再轉移即可。（這部分也可以最後用組合數學的同色球除掉）

最後注意前導零的狀态去除。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=19;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL dp[1<<maxn][102];
int num[30],tot=0;
bool vis[maxn];
int main(void){
    LL n,m;n=read();m=read();
    vector<LL>v;
    LL n1=n;
    while(n1){
        v.push_back(n1%10);
        n1/=10;
    }
    reverse(v.begin(),v.end());
    for(auto i:v) num[++tot]=i;
    dp[0][0]=1;
    n=tot;
    for(LL s=0;s<(1<<n);s++){
        memset(vis,0,sizeof(vis));
        for(LL j=1;j<=n;j++){
            if(s==(1LL<<(j-1))&&!num[j])  break;///去掉前導零
            if(!(s&(1LL<<(j-1)))||vis[num[j]]) continue;
            vis[num[j]]=1;///重複轉移,也可以組合方法除掉
            for(LL k=0;k<m;k++){
                dp[s][(k*10+num[j])%m]+=dp[s^(1LL<<(j-1))][k];
            }
        }

    }
    printf("%lld\n",dp[(1<<n)-1][0]);
   	return 0;
}