http://codeforces.com/contest/980/problem/D

cf.cpp

#include<bits/stdc++.h>
using namespace std;

int p[10005];
int tot;

const int p1 = 55566677;
const int p2 = 1000000007;
int ha[5005];
int lt[5005];
int cnt;

bool isPrime(int x)
{
	for (int i=2; i*i<=x; i++) {
		if (x%i==0) return false;
	}
	return true;
}

void getPrime()
{
	for (int i=2; i<=10000; i++) {
		if (isPrime(i)) p[tot++] = i;
	}
}

int getHash(int x)
{
	if (x==0) return -1;
	int h = 0;
	if (x<0) {
		h = (1ll*h*p1%p2-1+p2)%p2;
		x = -x;
	}
	for (int i=0; i<tot; i++) {
		int cnt = 0;
		while (x%p[i]==0) {
			cnt ^= 1;
			x /= p[i];
		}
		h = (1ll*h*p1%p2+cnt)%p2;
	}
	h = (1ll*h*p1%p2+x)%p2;
	return h;
}

int ans[5005];
int vis[5005];

int main()
{
	memset(lt, -1, sizeof(lt));
	getPrime();
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; i++)  {
		int x;
		scanf("%d", &x);
		ha[i] = getHash(x);
		for (int j=0; j<i; j++) {
			if (ha[i]==ha[j]) {
				lt[i] = lt[j];
				break;
			}
		}
		if (lt[i]==-1) lt[i]=cnt++;
	}
	for (int i=0; i<n; i++) {
		memset(vis, 0, sizeof(vis));
		int th = 0;
		int zero = 0;
		for (int j=i;j<n;j++) {
			if (ha[j]==-1) zero=1;
			if (vis[lt[j]]==0) {
				th ++;
				vis[lt[j]] = 1;
			}
			if (zero) {
				ans[max(th-1, 1)] ++;
			}
			else {
				ans[th] ++;
			}
		}
	}
	for (int i=1; i<=n; i++) printf("%d ", ans[i]);
	return 0;
}