1072: [SCOI2007]排列perm

Time Limit: 10 Sec Memory Limit: 128 MB

Description

　　给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能

被2整除，其中末位为2的有30种，末位为4的有60种。

Input

　　输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1

, 2, 3, 4, 5, 6, 7, 8, 9.

Output

　　每个数据仅一行，表示能被d整除的排列的个数。

Sample Input

7

000 1

001 1

1234567890 1

123434 2

1234 7

12345 17

12345678 29

Sample Output

1

3

3628800

90

3

6

1398

HINT

在前三个例子中，排列分别有1, 3, 3628800种，它们都是1的倍数。

【限制】

100%的数据满足：s的长度不超过10, 1<=d<=1000, 1<=T<=15

原题请戳

思路：

1.此题全排列可以水过。C++ algorithm库中的next_permutation可！以！水！过！

2.状压DP….但是我不太会。

看了一下题解

大概意思就是：先搞一个数字i，i对应的二进制数（如果对应位上的数是1的话）表示取了那位上的数字，j表示这些位上组合的值对b取余。f[i][j]即为已经取了对应i位上的数，再枚举一下k ，k显然不能曾经被取过（即在i这位上为1），就这样我们得出了状态转移方程：f[(1<< k)|i][(10*j+a[k])%b]+=f[i][j];

第一种思路：

//By: Sirius_Ren#include
     
      using namespace std;char s[15];int n,b,len,ans;int main(){    scanf("%d",&n);    while(n--){        cin>>(s+1)>>b;        ans=0;        len=strlen(s+1);        sort(s+1,s+len+1);        for(int i=1;i<=len;i++)s[i]-='0';        do{            register long long jy=0;            for(int i=1;i<=len;i++)jy=jy*10+s[i];            if(!(jy%b))ans++;        }while(next_permutation(s+1,s+len+1));        printf("%d\n",ans);    }}
     

第二种思路：

// by Sirius_Ren#include 
     
      #define ff(p,q,r,s) for(int i=p;i
     

最后给自己提个醒： pow（） 这个东西是非常非常慢的。。慎用慎用。

一个2000ms的程序最后跑了>10s 。足以体现这个函数跑得有多慢。