题目大意
将一个串划分为多个子集(不要求连续),要求同一子集内两任意元素的积为平方数。
定义一个串的答案为所需的最少子集个数。
一个长度为 \(n\) 的串有 \(\frac{n(n+1)}{2}\) 个非空子串,求答案为 \(1,2,3,\cdots ,n\) 的非空子串个数。
解题思路
结论:
若 \(ab\) 为平方数,\(bc\) 为平方数,则 \(ac\) 为平方数。
证明:
根据唯一分解定理,有:
\[a=\prod_{i=1}^{k}p_i^{a_i}\\ b=\prod_{i=1}^{k}p_i^{b_i}\\ c=\prod_{i=1}^{k}p_i^{c_i} \]上述 \(p_i\) 为质数。
因为 \(ab\) 为平方数,\(bc\) 为平方数,那么有:
\[\forall i\in[1,k],2|a_i+b_i\\ \forall i\in[1,k],2|b_i+c_i \]得:
\[\forall i\in[1,k],2|a_i+c_i \]那么 \(ac\) 为平方数。
证毕。
再看原题。
根据上面得结论,我们可以把 \(a_i \times a_j\) 为平方数的用并查集维护。
那么在同一个集内的数都满足两任意元素的积为平方数。
那么逐个区间求即可,时间复杂度 \(\mathcal O(n^2)\)。
注意 \(a_i=0\) 的情况。
CODE
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
const int _ = 5007;
int n, a[_], fa[_], vis[_], ans[_];
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
signed main()
{
n = read();
for(int i = 1; i <= n; ++i)
{
a[i] = read();
fa[i] = i;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j < i; ++j)
if(a[i] * a[j] > 0)
{
int tmp = (int)sqrt(a[i] * a[j]);
if(tmp * tmp == a[i] * a[j])
fa[find(j)] = find(i);
}
for(int i = 1; i <= n; ++i)
{
int tot = 0;
memset(vis, 0, sizeof vis);
for(int j = i; j <= n; ++j)
if(!a[j])
ans[max(1ll, tot)]++;
else
{
if(!vis[find(j)])
{
vis[find(j)] = 1;
tot++;
}
ans[tot]++;
}
}
for(int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
return 0;
}