【CF840C】On the Bench-DP+组合数学

测试地址：On the Bench
题目大意： 给出一个长为$n$的序列$A$，问有多少种$1$ ~ $n$的排列$p$，满足对于任意$1\le i<n$，有$A_{P_i}\cdot A_{P_{i+1}}$不为完全平方数。
做法： 本题需要用到DP+组合数学。
直接状压DP的复杂度应该是$O(n^2{2}^n)$的，肯定会爆，我们需要进一步发掘条件的性质。
我们发现两个数乘积为完全平方数这个性质有“传递性”，即若$a\cdot b$为完全平方数，$b\cdot c$为完全平方数，则$a\cdot c$也为完全平方数。证明的话，我们只需要分开来看每个质因子的幂次的奇偶性即可，根据条件，$a$和$c$的各质因子的幂次应该关于模$2$分别同余，而这也就意味着它们的幂次和一定为偶数，所以结论成立。
于是现在问题就简化为，有$tot$组数，共$n$个数，要排成一排，同组数之间不能相邻，问方案数。令第$i$组数中数的个数为$nu{m}_i$，我们考虑一组一组进行转移。
我们先忽略它们在最后整个排列中的绝对位置，只考虑它们目前的相对位置，即不考虑空格的存在。那么令$f(i,j)$为前$i$组数组成的排列中，不合法的相邻元素对数有$j$对（以下简称为不合法位置有$j$个）的方案数，我们考虑$f(i-1,j)$会对$f(i,x)$产生什么影响。
考虑第$i$组如何摆放。首先我们把这一组的数拆成$k$个连续段，这样这一组数内部会产生$nu{m}_i-k$个不合法位置，这一步的话，拆分有$C_{nu{m}_i-1}^{k-1}$种方案，而同组数内顺序可以互换，不会产生其他影响，因此还要乘上一个$nu{m}_i!$。拆完后，要把这$k$段插入到序列中，此时会对原来序列中的不合法位置产生一些影响。令插入到原来序列中不合法位置的段数为$l$，显然插入后不合法位置就会减少$l$，而这样插入的方案数应该为：$C_j^l\cdot C_{last+1-j}^{k-l}$，$last$表示前$i-1$组数中元素数量之和，也就是插入前序列的长度，那么上式应该就非常明显了：在$j$个不合法位置中选$l$个插入，剩下的在合法位置选一些位置插入，因此就是两个组合数的乘积。于是在枚举$k,l$的基础上，我们得到了$f(i-1,j)$的贡献：
$f(i-1,j)\cdot nu{m}_i!\cdot C_{nu{m}_i-1}^{k-1}\cdot C_j^l\cdot C_{last+1-j}^{k-l}$
而进行完这一些操作后，不合法位置数目变为$j+nu{m}_i-k-l$，因此这个贡献应该累加在$f(i,j+nu{m}_i-k-l)$中。于是最后的答案就是$f(tot,0)$了。
上面的转移方程看上去是$O(n^4)$的（$i,j,k,l$），但因为$k$枚举的范围只到$nu{m}_i$，因此实际上时间复杂度为$O(n^3)$，可以通过此题。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int n,num[310],sum[310],tot=0,belong[310];
ll a[310],f[310][310],fac[310],C[310][310];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		belong[i]=i;
		scanf("%lld",&a[i]); 
	}
	
	for(int i=1;i<=n;i++)
		if (belong[i]==i)
		{
			num[++tot]=1;
			for(int j=i+1;j<=n;j++)
			{
				ll s=(ll)sqrt((double)(a[i]*a[j])+0.5);
				if (s*s==a[i]*a[j]) belong[j]=i,num[tot]++;
			}
			sum[tot]=sum[tot-1]+num[tot];
		}
	
	fac[0]=1;
	for(ll i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	C[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
	
	f[0][0]=1;
	for(int i=1;i<=tot;i++)
	{
		for(int j=0;j<=max(0,sum[i-1]-1);j++)
			for(int k=1;k<=min(num[i],sum[i-1]+1);k++)
				for(int l=0;l<=min(j,k);l++)
				{
					ll nxt=f[i-1][j]*fac[num[i]]%mod;
					nxt=nxt*C[num[i]-1][k-1]%mod;
					nxt=nxt*C[j][l]%mod;
					if (k-l>sum[i-1]+1-j) continue;
					nxt=nxt*C[sum[i-1]+1-j][k-l]%mod;
					f[i][j+num[i]-k-l]=(f[i][j+num[i]-k-l]+nxt)%mod;
				}
	}
	printf("%lld",f[tot][0]);
	
	return 0;
}

最后

以上就是糟糕身影为你收集整理的【CF840C】On the Bench-DP+组合数学的全部内容，希望文章能够帮你解决【CF840C】On the Bench-DP+组合数学所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。