首页 > 资讯 > C++ > 正文

[BZOJ 1072][SCOI 2007]排列perm

14-12-06 来源：[db:作者]

收藏我要投稿

这题范围小，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 
#include 
#include 
#include 
#include 
 
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 
 
 
 
??

点击复制链接与好友分享!回本站首页