【NOIP提高A组模拟2018.8.18】 number

【题目描述】

给定正整数 n,m，问有多少个正整数满足：

 (1)不含前导 0；

 (2)是 m 的倍数；

 (3)可以通过重排列各个数位得到 n。

【输入格式】

一行两个整数 n，m。

【输出格式】

一行一个整数表示答案对 998244353 取模的结果。

【样例输入】

1 1

【样例输出】

1

【数据规模】

对于 20%的数据，n<10^10。

对于 50%的数据，n<10^16，m<=20。

对于 100%的数据，n<10^20，m<=100。

 

分析：

数位DP。

状压记录 0 到 9 剩余个数以及 mod m 的值的情况下的方 案数。转移时枚举最高位填的数字，最后一次转移不要枚 举 0。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long c[12],b[12],dp[65535][117],w[12];
int a[12],m;
string s;
int main(){
    cin>>s>>m;
    int len=s.size();
    for(int i=0; i<len; i++) a[s[i]-'0']++;
    c[0]=1;
	b[0]=c[0]*a[0];
    for (int i=1; i<=9; i++){
		c[i]=b[i-1]+1;b[i]=b[i-1]+c[i]*a[i];
    } 
    for(int i=1; i<=9; i++)
		if (a[i]>0) dp[c[i]][i%m]=1;
    for (int i=1; i<=b[9]; i++){
		int x=i;
        for(int j=9; j>=0; j--) w[j]=a[j]-(x/c[j]),x%=c[j];
        for(int j=0; j<=9; j++) 
			if(w[j]>0)for(int k=0;k<=m-1;k++){
				dp[i+c[j]][(k*10+j)%m]+=dp[i][k]+mod;
				dp[i+c[j]][(k*10+j)%m]%=mod;
			} 
    }
    cout<<dp[b[9]][0]<<endl;
}