首页 > 代码库 > [bzoj1072][SCOI2007]排列perm

[bzoj1072][SCOI2007]排列perm

2024-09-06 19:48:16   216人阅读

给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）

s的长度<=10    d<=1000  数据组数<=15

非常奇妙的一道题，题目的样例居然还告诉了你总共最多有多少种排列......

算了算...10!*15 才5000多万，貌似可以暴力！！

于是就写了一个按数字串的每一位搜索的暴力上去，T了.....

然后考虑了一下，发现同一位没必要搜相同数字啊....然后就改成了搜一位放什么数字....

然后瞬间就过了。

技术分享

复杂度最大应该就是10!*15=54432000  如果15组数据都是0-9的话可能可以卡掉.. 

正确的解法应该是壮压dp，用f[i][j]表示i状态下余数为j的方案数量，复杂度只有2^10*1000*15=15360000

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
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;
}

char ch;
int d,n,ans;
int s[14];
int num[15];

void dfs(int i,ll x)
{
    if(i>n){if(x%d==0)ans++;return;}
    for(int j=0;j<=9;j++)
        if(num[j]){--num[j];dfs(i+1,x*10+j);++num[j];}
}

int main()
{
    int T=read();
    while(T--)
    {
        memset(num,0,sizeof(num));
        n=0;while((ch=getchar())!=‘ ‘) s[++n]=ch-‘0‘,++num[s[n]];
        d=read();ans=0;dfs(1,0);
        printf("%d\n",ans);
    }
    return 0;
}

 

[bzoj1072][SCOI2007]排列perm


联系
我们