思路：狀壓dp，f[i][j]表示新的排列的狀態為i(也就是新的排列已經選了哪些數），然后模d的余數為j的方案數。

但考慮到可能有些數會出現多次，假設一個數x出現了cnt[x]次，那么對于一個可行的答案，顯然也包含cnt[x]個x，那么這樣的答案就會被計算多次，因為如果狀態i先加入第一個x再加入第二個x和狀態i先加入第二個x再加入第一個x顯然是算作兩種不同的方案，但其實他們是一樣的，但對于某一個確定的合法的答案，x的位置不會變，因此如果重復的情況只可能是該答案中所有的x在互換，這種互換會被多次統計但答案其實只有一個，可以發現這種互換的情況數有cnt[x]!種（本質上就是一個長為cnt[x]的排列的情況數），然后答案除以cnt[x]！就可以完成去重了。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define maxn 1<<11int cases,p; int cnt[15],f[maxn][maxn]; char s[15];int main(){scanf("%d",&cases);while (cases--){scanf("%s%d",s,&p);int n=strlen(s);memset(f,0,sizeof(f)),f[0][0]=1,memset(cnt,0,sizeof(cnt));for (int i=0;i<n;i++) cnt[s[i]-'0']++;for (int i=0;i<(1<<n);i++)for (int m=0;m<p;m++)for (int j=0;j<n;j++)if (!(i&(1<<j))) f[i|(1<<j)][(m*10+s[j]-'0')%p]+=f[i][m];int ans=f[(1<<n)-1][0];for (int i=0;i<=9;i++)for (int j=2;j<=cnt[i];j++)ans/=j;printf("%d\n",ans);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/DUXT/p/5990741.html

總結

以上是生活随笔為你收集整理的bzoj1072: [SCOI2007]排列perm的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。