Codeforces 980D

这题其实挺水的，但我比较vegetable，交了好多次才过。

题意：

给定一个序列，把这个序列的所有连续子序列分组，每组中任意两个数相乘是个完全平方数，输出每个子序列最少分的组数；

思路：

先把每个数都除去自身的完全平方因子，为什么呢？这样处理了之后，只有相同的数相乘才能变成完全平方数，而且原来相乘能变成完全平方数的数对也不会有影响，举个例子：$ 1 \times 4 = 4 $，$4$是完全平方数，除去平方因子后，变成 $1 \times 1 = 1$，$1$还是完全平方数（感性地理解YY一下就好了）

把处理完的数列从小到大排序，再离散化（防止数字太大，爆MLE）

由于题目给定n的范围是$5000$，所以不能$ O(n^3) $爆扫，QXZ大佬介绍了一种非常gin的方法，我用了离散化+桶的方法；

开个桶bo[i][j]表示1到i中数值为j的个数；然后dp，f[i][j]表示i到j的数列需要分成几个区间，f[i][j]=f[i][j-1]，当第j个数在i到j中唯一时，f[i][j]++；

需要注意的点：

1、除去平方因子时要用while或者倒着扫i，防止有多个平方数；

2、排序时，要记录原来的位置，离散化完要排列回原来的序列（要按原来给定序列的子序列，而且子序列在原序列中是连续的）

3、0要特判，当0为一个单独的子序列时自成一组，否则与其他任何数都能变成完全平方数（和任何数都能一组）

附上蒟蒻的代码：

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 struct rec

 {

     int place,num;

 }a[MAXN],now;

 bool comp1(const rec &x,const rec &y)

 {

     return x.num<y.num;

 }

 bool comp2(const rec &x,const rec &y)

 {

     return x.place<y.place;

 }

 int n,bo[MAXN][MAXN],f[MAXN][MAXN],ans[MAXN],special0;

 bool special[MAXN];

 main()

 {

     scanf("%d",&n);

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

     {

         scanf("%d",&a[i].num);

         a[i].place=i;

     }

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

     {

         if(a[i].num!=)

         {

             int k=sqrt(abs(a[i].num));

             for(int j=k;j>=;--j)

             while(a[i].num%(j*j)==)

             {

                 a[i].num/=j*j;

             }

         } else

         {

             special[i]=true;

             special0=i;

         }

     }

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

     now.place=;

     now.num=a[now.place].num;

     a[now.place].num=;

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

     {

         if(a[i].num==now.num)

         {

             a[i].num=a[now.place].num;

         } else

         {

             now.place=i;

             now.num=a[i].num;

             a[i].num=a[i-].num+;

         }

     }

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

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

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

         bo[j][a[i].num]++;

     special0=a[special0].num;

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

     {

         f[i][i]=;

         ++ans[f[i][i]];

     }

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

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

         {

             f[i][j]=f[i][j-];

             if(bo[j][a[j].num]-bo[i-][a[j].num]==&&(!special[j])&&(((bo[j][special0]-bo[i-][special0]!=j-i)||special0==)))

                 ++f[i][j];

             ++ans[f[i][j]];

         }

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

         printf("%d ",ans[i]);

     return ;

 }