【BZOJ1072】排列（搜索）

题面

题解

算下复杂度，如果用\(next\_permutation\)

那就是\(10!\times 10\times 15\)，复杂度不太对

那好办啊，把\(next\_permutation\)改成搜索不就完了。。

#include<iostream>

#include<cstring>

using namespace std;

char ch[15];

int a[10],d,ans,n;

void dfs(int x,int r)

{

	if(x==n+1){ans+=r==0;return;}

	for(int i=0;i<=9;++i)

		if(a[i])--a[i],dfs(x+1,(r*10+i)%d),++a[i];

}

int main()

{

	ios::sync_with_stdio(false);

	int T;cin>>T;

	while(T--)

	{

		cin>>(ch+1)>>d;ans=0;n=strlen(ch+1);

		for(int i=n;i;--i)++a[ch[i]-48];

		dfs(1,0);cout<<ans<<endl;

		a[0]=a[1]=a[2]=a[3]=a[4]=a[5]=a[6]=a[7]=a[8]=a[9]=0;

	}

	return 0;

}

巴特西

【BZOJ1072】排列（搜索）

【BZOJ1072】排列（搜索）

题面

题解

最新文章

热门文章