luogu P4448 [AHOI2018初中组]球球的排列

这道题我一上来只会80

还是要感谢题解区大佬题解的帮助

先考虑若\(xy,xz\)为完全平方数,则\(yz\)也为完全平方数,因为\(xy*xz=x^2yz\)为完全平方数,除掉\(x^2\)就行了

所以所有两两乘积为完全平方数的数可以放在一个集合中,用并查集合并即可.

若每个并查集都是一种颜色,所以现在问题变成有\(m\)种颜色的互不相同的球,每种颜色的球有\(b_i\)个,问多少种球的排列满足同色球不相邻

先把所有球按颜色大小排个序,然后考虑dp,设\(f[i][j][k]\)表示前\(i\)个球,有\(j\)个和\(i\)不同色且相邻的同色球对数,有\(k\)个和\(i\)同色且相邻的同色球对数的方案

如果当前球与上一个球不同色,那么考虑把这个球插入到同色球之间,方案为\(f[i-1][k][j-k+1]*(j+1)\)

插到异色球中,方案为\(f[i-1][k][j-k]*(i-j)\)

如果该球与上一个球颜色相同,这里先设\(cnt\)表示前面放了几个这样颜色的球

把这个球插到和这个球同色的球旁边,方案为\(f[i-1][j][k-1]*(cnt*2-(k-1))\)

插到其他同色球之间,方案为\(f[i-1][j+1][k]*(j+1)\)

插到其他异色球之间,方案为\(f[i-1][j][k]*(i-(cnt*2-k+j))\)

答案就是\(f[n][0][0]\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<complex>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#define LL long long

#define il inline

#define re register

using namespace std;

const LL mod=1000000007;

il LL rd()

{

    re LL x=0,w=1;re char ch;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n;

LL a[310],f[2][310][310];

int fa[310];

int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}

void merg(int x,int y){fa[findf(y)]=findf(x);}

int main()

{

  n=rd();

  for(int i=1;i<=n;i++) a[i]=rd(),fa[i]=i;

  for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

      {

    	if(findf(i)==findf(j)) continue;

    	LL mu=a[i]*a[j],sq=sqrt(mu);

    	if(sq*sq==mu) merg(i,j);

      }

  for(int i=1;i<=n;i++) a[i]=findf(i);

  sort(a+1,a+n+1);

  int now=1,la=0;

  f[0][0][0]=1;

  for(int i=1,cnt=0;i<=n;i++)

    {

      memset(f[now],0,sizeof(f[now]));

      if(a[i]!=a[i-1])

    	{

    	  cnt=0;

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

	        {

	          for(int k=0;k<=j+1;k++)

	    	    {

		          if(k<=j) f[now][j][0]=(f[now][j][0]+(f[la][k][j-k]*(i-j))%mod)%mod;

		          f[now][j][0]=(f[now][j][0]+(f[la][k][j-k+1]*(j+1))%mod)%mod;

		        }

	        }

    	}

        else

	      {

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

	          for(int k=0;k<=cnt;k++)

	            {

	        	  if(k>0) f[now][j][k]=(f[now][j][k]+(f[la][j][k-1]*(cnt*2-(k-1)))%mod)%mod;

		          if(i-(cnt*2-k+j)>0) f[now][j][k]=(f[now][j][k]+(f[la][j][k]*(i-(cnt*2-k+j)))%mod)%mod;

		          f[now][j][k]=(f[now][j][k]+(f[la][j+1][k]*(j+1))%mod)%mod;

	            }

	       }

      now^=1,la^=1;

      ++cnt;

    }

  printf("%lld\n",f[la][0][0]);

  return 0;

}

巴特西

luogu P4448 [AHOI2018初中组]球球的排列

最新文章

热门文章