程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj1072【SCOI2007】排列perm

bzoj1072【SCOI2007】排列perm

編輯:C++入門知識

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

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

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>

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved