【做题】Codeforces Round #429 (Div. 2) E. On the Bench—

题目大意是给你n个数，求相邻两数相乘不是完全平方数的排列数。

一开始看到这题的时候，本人便想给相乘为完全平方数的数对建边，然后就写萎了...

后来通过集体智慧发现这个重要性质：对于自然数a,b,c，若a*b为完全平方数，且b*c为完全平方数，那么a*c就是完全平方数。（我居然没想到）因此就可以对这n个数进行分组，使得每一组中两个数两两相乘为完全平方数，不同组的数两两相乘不是完全平方数。假设分成tot组，第i组的数的个数为num[i]。这也就等同于相同的数不能相邻的排列问题。

于是通过PY就得到了动规的做法：

定义数组dp[i,j]，其中i表示前i组数，j表示有多少对相邻的同组的数（这也等价于有j个地方需要插入其他的数），而dp[i,j]就表示在当前状态下的方案数。那么最终答案就是dp[tot,0]。

定义m为前i-1组数的元素个数之和，在dp过程中维护。

当新加入第i组数的时候，把这num[i]个数分成k份（方案数是C(num[i]-1,k-1)），插入到m+1个空位中。

此时需要分类讨论：

在这m+1个空位中，有j个空位是特殊的，若插入其中会影响新生成的排列的相邻同组数的数目。于是设k份中的p份插入这j个空位中，剩下k-p份插入m+1-j个空位中。

就可以得到dp[i,j+num[i]-k-p]+=dp[i-1,j]*C(num[i-1],k-1)*C(j,p)*C(m+1-j,k-p);

这我一开始也不是很理解...

当然代码与这里有所差异。

注：因为dp是基于每一组数中的元素相同的前提的，所以最后答案还要乘以每一组数的A(num[i],num[i])。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=,MOD=;

 long long num[N],c[N][N];

 long long dp[N][N],a[N];

 int tmp,n,tot,example[N];

 bool key;

 bool ask(int x,int y)

 {

     long long re=;

     re*=x;

     re*=y;

     long long f=sqrt(re);

     if(f*f==re) return ;

     return ;

 }

 int main()

 {

     cin>>n;

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

     {

         cin>>tmp;

         key=;

         for(int j=;j<=tot;j++)

         {

             if(ask(tmp,example[j]))

             {

                 num[j]++;

                 key=;

                 break;

             }

         }

         if(key)

         {

             num[++tot]=;

             example[tot]=tmp;

         }

     }

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

      c[i][]=;

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

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

      {

          c[i][j]=c[i-][j]+c[i-][j-];

          c[i][j]%=MOD;

      }

     int m=;

     a[]=;

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

     {

         a[i]=a[i-]*i;

         a[i]%=MOD;

     }

     dp[][]=;

     long long temp,temp1;

     for(int i=;i<=tot;i++)

     {

         for(int j=;j<n&&j<=m+;j++)

         {

             if(dp[i-][j]==) continue;

             for(int k=;k<num[i];k++)

             {

                 temp=dp[i-][j]*c[num[i]-][k];temp%=MOD;

                 for(int p=;p<=k+&&p<=j+num[i]--k;p++)

                 {

                     temp1=temp*c[j][p];temp1%=MOD;//本人因为数据溢出炸了几次

                     dp[i][j+num[i]--k-p]+=(temp1*c[m+-j][k+-p])%MOD;

                     dp[i][j+num[i]--k-p]%=MOD;

                 }

             }

         }

         m+=num[i];

     }

     for(int i=;i<=tot;i++)

     {

         dp[tot][]*=a[num[i]];

         dp[tot][]%=MOD;

     }

     cout<<dp[tot][]<<endl;

     return ;

 }

巴特西

【做题】Codeforces Round #429 (Div. 2) E. On the Bench——组合问题+dp

最新文章

热门文章