luogu P4448 [AHOI2018初中组]球球的排列-白红宇

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

阅读量：4559 次

发布时间：2019-06-08

本文共 1922 字，大约阅读时间需要 6 分钟。

这道题我一上来只会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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #define LL long long#define il inline#define re registerusing 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
              
               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;}

转载于:https://www.cnblogs.com/smyjr/p/9440949.html

你可能感兴趣的文章

ORA-12505: TNS: 监听程序当前无法识别连接描述符中所给出的SID等错误解决方法