题解 CF840C On the Bench

Find_Yourself · 2023-05-10 13:52:07 · 题解

更好的阅读体验

这是一篇简洁易懂的良心题解，提供了多种做法。

对于两个数 x,y，定义 x=n^2 \cdot tx,y=m^2 \cdot ty。如果 x\cdot y 为平方数，则说明 tx=ty。所以我们可以将每个数除去其平方因子，比较相邻两数是否相等即可。

F1：

定义 f_{i,j,k} 为插入 i 个数、有 j 对相邻相等的数、有 k 对相邻且与 a_i 相等的数。

定义 s_i 为在插入第 i 个数之前有多少个数与 a_i 相等。

转移分三种情况讨论：

实现时可以把 a 数组排序，如果 a_i \neq a_{i-1}，则将 f_{i-1,j,k} 全部加到 f_{i-1,j,0} 上，并清 0。

可以把第一维滚掉。复杂度 O(n^3)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300+5,mod=1e9+7;
ll n,a[N],f[2][N][N];
void fen(ll &x){
  for(ll i=2;i*i<=x;++i){
    while(x%(i*i)==0){
      x/=i*i;
    }
  }
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;for(int i=1;i<=n;++i){cin>>a[i];fen(a[i]);}
  sort(a+1,a+n+1);
  int t=0,cnt=0;f[0][0][0]=1;
  for(int i=1;i<=n;++i){
    if(a[i]!=a[i-1]){
      for(int j=0;j<i;++j){
        for(int k=1;k<=min(j,cnt);++k){
          f[t^1][j][0]=(f[t^1][j][0]+f[t^1][j][k])%mod;
          f[t^1][j][k]=0;
        }
      }
      cnt=0;
    }
    for(int j=0;j<i;++j){
      for(int k=0;k<=min(cnt,j);++k){
        ll tmp=0;
        if(j&&k)tmp=f[t^1][j-1][k-1]*(2*cnt-k+1)%mod;
        tmp=(tmp+f[t^1][j][k]*(i-2*cnt+2*k-j)%mod+f[t^1][j+1][k]*(j-k+1)%mod)%mod;
        f[t][j][k]=(f[t][j][k]+tmp)%mod;
      }
    }
    ++cnt;memset(f[t^1],0,sizeof(f[t^1]));t^=1;
  }
  cout<<f[t^1][0][0]<<endl;
  return 0;
}

F2：

考虑将相同的数作为一个整体，切成多块插入。

定义 f_{i,j} 为前 i 组数插入后有 j 对相同相邻数的方案数。

定义 g_{i,j} 为 i 个不同的数分成 j 组的方案数。

定义 s_i 为第 i 组有多少数，k 为将第 i 组数分成几部分插入，sum_i 为 \sum\limits_{i=1}^{i}s_i，p 为插入 k 部分后有几对原来相邻相同的数断开了。