首页 > 代码库 > [BZOJ 1072][SCOI 2007]排列perm
[BZOJ 1072][SCOI 2007]排列perm
题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1072
这题范围小,s的长度不超过10,如果用二进制表示每一位数字是否被选择到的话,二进制最大不超过2^10,可以用状压DP做。
我们把这题分两步走
第一步,把输入的字符串s中所有的数字都当成不同的,在这种情况下求出方案总数
用f[S][j]表示当前每一位数字是否选到的二进制状态为S,拼出的数mod d=j的方案数。
决策就是可以从所有没有被选到的数字中,选择一个数放到之前拼好的数字后面,组成新的数。
如果原来的数mod d=j的话,那么很容易想到新的数mod d=(j*10+新加入的数)mod d
第二步,由于我们第一步把所有数字都当成不相同的了,但是这样做相同的数字会造成重复,若数字x(0<=x<=9)在字符串中出现了t次,那么数字x引起重复t!次。
把0~9的所有数字遍历一遍,除掉每个数字造成的重复。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; int d,cnt[11],f[3010][1010]; //f[S][j]=当前选取数字的二进制状态为S,mod d=j的方案数 char s[11]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%s%d",s,&d); int len=strlen(s); memset(f,0,sizeof(f)); memset(cnt,0,sizeof(cnt)); for(int i=0;i<len;i++) cnt[s[i]-'0']++; f[0][0]=1; //初始化:0 mod d=0的方案数有1种 for(int S=0;S<(1<<len);S++) //状态的二进制集合S for(int i=0;i<d;i++) //number mod d=i if(f[S][i]) for(int j=0;j<len;j++) //决策时,要选一个当前状态S没有选到的数字,加入到原来的数字后面 if(!(S&(1<<j))) f[S|(1<<j)][((i*10)+s[j]-'0')%d]+=f[S][i]; int ans=f[(1<<len)-1][0]; for(int i=0;i<10;i++) //去除重复,数字i出现了n次,则其重复次数为n! for(int j=1;j<=cnt[i];j++) ans/=j; printf("%d\n",ans); } return 0; }
[BZOJ 1072][SCOI 2007]排列perm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。