P4163 [SCOI2007]排列

##P4163 [SCOI2007]排列

本着来写状压的，奈何发现手算一波复杂度后感觉不对。

那么我们考虑搜索（$n\leq10$），暴力搞的话复杂度为 $\text{O}(n!\times T)$，无法通过。

那么我们考虑使用一点点的状压思想和搜索技巧：

我们枚举状态为一个 n 位的二进制数 $s_1$，表示在二进制下的意义选取了哪些数位（类似于一个集合，0 表示未选，1 表示已选）。特殊地，我们保证其中恰好有 $\lfloor\frac{n}{2}\rfloor$ 个数位为 1，而其余的数位均为 0；那么，相应地，我们对于 $s_1$ 进行按位取反，那么得到的另一个 n 位的二进制数 $s_2$ 表示未选的数位所构成的一个集合。

此时，我们将会得到两个集合共同表示一些方案，即我们选定的一个排列中，前 $\lfloor\frac{n}{2}\rfloor$ 个数位来自 $s_1$，剩余的 $\lceil\frac{n}{2}\rceil$ 个数位来自 $s_2$。那么我们对于来自 $s_1$ 的数位和来自 $s_2$ 的数位分别进行排列，那么我们将得到的排列对 $d$ 取模后的结果分别存在两个集合 $t_1,t_2$ 中，那么此时，当 $t_1$ 中的所得结果和 $t_2$ 中的所得结果拼凑起来恰好能被 $d$ 整除的即为合法方案，即 $\text{Ans} = \sum_{i=0}^{d-1} t_1[i]\times t_2[(d-i)\pmod{d}]$。这个小的搜索技巧名为 “折半搜索”。

那么此时我们得到的算法的时间复杂度为 $\text{O}\Big(2^{(\lfloor\frac{n}{2}\rfloor)}\times(\lfloor\frac{n}{2}\rfloor)!\times(\lceil\frac{n}{2}\rceil)!\times T\Big)$。

除了 $\text{dfs}$ 会使得常数较大以外，其实效率还是挺不错的。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7;

string s;
lint Map[1010][2],mo[11],a[11],b[11],c[11],d[11],e[11],Ans=0;
int n,mod,ch,tmp,top;

void Dfs1(lint f,int dep){
	if(dep==top){
		++Map[(f*tmp)%mod][ch];
		return;
	}
	for(int i=0;i<10;i++) if(b[i]){
		--b[i],Dfs1((f+(i*mo[dep]%mod))%mod,dep+1),++b[i];
	}
	return;
}

void Dfs2(int dep,int last){
	if(dep==(n/2)){//代码长得丑主要是为了处理 Dfs 枚举排列时的去重
		memset(Map,0,sizeof(Map)),memset(b,0,sizeof(b));
		for(int i=0;i<dep;i++) ++b[d[i]];
		top=n/2,ch=0,tmp=mo[n-(n/2)],Dfs1(0,0);
		for(int i=0;i<10;i++) b[i]=e[i]-b[i];
		top=n-(n/2),ch=1,tmp=1,Dfs1(0,0);
		for(int i=0;i<mod;i++) Ans+=Map[i][0]*Map[(mod-i)%mod][1];
		return;
	}
	for(int i=last;i<10;i++) if(c[i]) --c[i],d[dep]=i,Dfs2(dep+1,i),++c[i];
	return;
}

void Solve(){
	cin>>s>>mod;
	memset(a,0,sizeof(a)),memset(c,0,sizeof(c));
	n=s.length(),Ans=0;
	for(int i=0,x=1;i<n;i++) mo[i]=x%mod,(x*=10)%=mod,a[i]=s[i]-'0',++c[a[i]];
	//注意到拼凑两个排列时我们得到的是一个数，所以需要预处理 10 的幂
	for(int i=0;i<10;i++) e[i]=c[i];
	Dfs2(0,0);
	printf("%lld\n",Ans);
	return;
}

int main(void){

	int T=readint;
	while(T--) Solve();

	return 0;
}