bestcoder——数组划分

Abelian Period

 

 Accepts: 400

 

 Submissions: 961

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 262144/131072 K (Java/Others)

Problem Description

Let $S$ be a number string, and $occ(S,x)$ means the times that number $x$ occurs in $S$.

i.e. $S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1$.

String $u,w$ are matched if for each number $i$, $occ(u,i)=occ(w,i)$ always holds.

i.e. $(1,2,2,1,3)\approx (1,3,2,1,2)$.

Let $S$ be a string. An integer $k$ is a full Abelian period of $S$ if $S$ can be partitioned into several continous substrings of length $k$, and all of these substrings are matched with each other.

Now given a string $S$, please find all of the numbers $k$ that $k$ is a full Abelian period of $S$.

Input

The first line of the input contains an integer $T(1\le T\le 10)$, denoting the number of test cases.

In each test case, the first line of the input contains an integer $n(n\le 100000)$, denoting the length of the string.

The second line of the input contains $n$ integers S_1,S_2,S_3,...,S_n(1\leq S_i\leq n)S​1​​,S​2​​,S​3​​,...,S​n​​(1≤S​i​​≤n), denoting the elements of the string.

Output

For each test case, print a line with several integers, denoting all of the number $k$. You should print them in increasing order.

Sample Input

Copy

2
6
5 4 4 4 5 4
8
6 5 6 5 6 5 5 6

Sample Output

3 6
2 4 8

Statistic |  Submit |  Clarifications |  Back

先找其所有约数，然后对每一个约数进行逐一判断

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 2009
#define INF 9999999999999
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  long long ll;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
ll my_min(ll x,ll y){ return x>y?y:x;};

int main()
{
	int t;
	int n;
	int a[100005];
	int b[100005];
	while(scanf("%d",&t)!=EOF)
	{
		for(int k=1;k<=t;k++)
		{
			int len = 0;
			memset(b,0,sizeof(b));
			memset(a,0,sizeof(a)); 
			scanf("%d",&n);
			for(int i=1;i<=n;i++)
				scanf("%d",&a[i]);
				
			for(int i=1;i<=n-1;i++)//找到约数
			{
				if(n%i==0)
					b[len++] = i;
			}
			//for(int i=1;i<len;i++)
			//	printf("%d ",b[i]);
			//printf("\n");
			
			
			for(int i=0;i<len;i++)
			{
				
				int t1[100005];
				int t2[100005];
				int len1 = n/b[i];
				
				int flag ;
				flag = 1;
				for(int j=1;j<len1;j++)//判断
				{

					for(int i1 = (j-1)*b[i]+1;i1<=j*b[i];i1++)
					{
						t1[i1-(j-1)*b[i]] = a[i1];
					}
					for(int i1 = j*b[i]+1;i1 <= (j+1)*b[i];i1++)
					{
						t2[i1 - j*b[i]] = a[i1];
					}
					sort(t1+1,t1+1+b[i]);
					sort(t2+1,t2+1+b[i]);
					int i1;
					for(i1=1;i1<=b[i];i1++)
					{
						if(t1[i1]!=t2[i1])
						{
							break;
						}
					}
					
					if(i1!=b[i]+1)
					{
						flag = 0;
					}
				}
				if(flag)
					printf("%d ",b[i]);
			}
			
			printf("%d\n",n);
		}
	}
    return 0;
}