bzoj1072【SCOI2007】排列perm

bzoj1072【SCOI2007】排列perm

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

Sample Output

HINT

在前三個例子中，排列分別有1, 3, 3628800種，它們都是1的倍數。

【限制】

100%的數據滿足：s的長度不超過10, 1<=d<=1000, 1<=T<=15

Source

狀壓DP題目

f[i][j]表示狀態為i，余數為j的方案數。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
using namespace std;
int t,d,n,ans;
int f[1050][1005],cnt[20],fac[20],g[1050],p[20];
char s[20];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int calc(int x)
{
	int ret=0;
	while (x){ret+=x&1;x>>=1;}
	return ret;
}
inline void dp(int x)
{
	F(i,0,n-1) if ((1<<i)&x) ans="f[(1<<n)-1][0];" int="" n="strlen(s);" pre="" t="read();" tmp="p[g[x]-1]%d*(s[i]-'0')%d;" while=""><p>
</p>
   
</i)&x)></algorithm></cstdlib></cmath></cstring></cstdio></iostream>