[BZOJ 1072][SCOI 2007]排列perm

[BZOJ 1072][SCOI 2007]排列perm

這題范圍小，s的長度不超過10，如果用二進制表示每一位數字是否被選擇到的話，二進制最大不超過2^10，可以用狀壓DP做。

我們把這題分兩步走

第一步，把輸入的字符串s中所有的數字都當成不同的，在這種情況下求出方案總數

用f[S][j]表示當前每一位數字是否選到的二進制狀態為S，拼出的數mod d=j的方案數。

決策就是可以從所有沒有被選到的數字中，選擇一個數放到之前拼好的數字後面，組成新的數。

如果原來的數mod d=j的話，那麼很容易想到新的數mod d=(j*10+新加入的數)mod d

第二步，由於我們第一步把所有數字都當成不相同的了，但是這樣做相同的數字會造成重復，若數字x(0<=x<=9)在字符串中出現了t次，那麼數字x引起重復t!次。

把0~9的所有數字遍歷一遍，除掉每個數字造成的重復。

#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
int d,cnt[11],f[3010][1010]; //f[S][j]=當前選取數字的二進制狀態為S，mod d=j的方案數
char s[11];
 
int main()
{
    int T;
    scanf(%d,&T);
    while(T--)
    {
        scanf(%s%d,s,&d);
        int len=strlen(s);
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i
 
 
 
 
??