codeforces 401D Roman and Numbers

      题目大意：给出n和m，求有多少数字满足三个条件：1、由n各位数字打乱重组而成；2、没有先导0；3、能整除m。

      输入：一行两个整数n(1<=n<10^18)和m(1<=m<=100)。

      输出：一行一个整数表示答案。

      题解：

      状压DP可过。

      考虑每一位，用一组桶记录下这一位使用某一个数字能产生的模m的余数分别有多少个。为了保证这个数字之前没用过，使用状压DP进行转移。具体来说，f[i][j]表示当前状态为i（也就是使用了对应位数的数字），模m的余数为j的数字的个数。每次转移的时候，枚举每一位，例如枚举到第k位且第k位为1，则f[i][j]+=f[i^(1<<k)][(m+j-p[a][b])%m]，其中a为这一位的数字，b为当前位数，p[a][b]表示a*10^b模m的余数。这样写的意义是，后面的数字的余数要加上这一位数字模m的余数，因此桶中的数字应该整体移动模m的余数位。为了防止先导0，在发现当前在转移满状态时，特判一下，如果这一位是0就不去转移它，就没有了第一位是0的情况数。最后将f[满状态][0]取出，因为数字有重复，重复的方案数为每个数字的数量的阶乘的乘积，所以答案除以这个数字即可。

      （当时因为使用的是virtual，并没有意识到cf不能用lld的事实，并因此WA了三发……心态炸裂）

      代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;

LL n;
int m,cnt;
int s[20],p[20][102],ss[10];
LL aa,f[262150][102],jc[20];

int main()
{
	int x=0,x1=0,x2=0;
	LL a=0;
	cin>>n>>m;
	a=n;while(a){s[++cnt]=a%10;a/=10;}
	jc[0]=1;for(int i=1;i<=cnt;i++) jc[i]=jc[i-1]*i;
	for(int i=1;i<=cnt;i++) for(int j=0;j<=100;j++){a=s[i];for(int k=1;k<=j;k++) a*=10;p[i][j]=a%m;}
	a=(1<<cnt)-1;for(int j=0;j<10;j++) ss[j]=0;
	x1=0;while(a){x1++;if(a&1) ss[s[x1]]++;a>>=1;}
	aa=1;for(int j=0;j<10;j++) aa*=jc[ss[j]];
	for(int i=1;i<(1<<cnt);i++)
	{
	   a=i;x1=x2=0;while(a){if(a&1) x2++;a>>=1;x1++;}
	   if(x2==1){f[i][s[x1]%m]=1;continue;}
	   for(int j=0;j<x1;j++)
	   {
	   	  a=i^(1<<j);
	   	  if(x2==cnt&&!s[j+1]) continue;
	   	  for(int k=0;k<m;k++)
	   	  {
	   	  	 f[i][k]+=f[a][(m+k-p[j+1][x2-1])%m];
		  }
	   }
	}
	cout<<f[(1<<cnt)-1][0]/aa<<endl;
	return 0;
}

最后

以上就是无限大树为你收集整理的codeforces 401D Roman and Numbers的全部内容，希望文章能够帮你解决codeforces 401D Roman and Numbers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。