Abelian Period

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5908

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)≈(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≤T≤10), denoting the number of test cases.

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

The second line of the input contains n integers S1,S2,S3,...,Sn(1≤Si≤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

2

6

5 4 4 4 5 4

8

6 5 6 5 6 5 5 6

Sample Output

3 6

2 4 8

Hint

题意

设S是一个数字串，定义函数occ(S,x)表示S中数字x的出现次数。

例如：S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1。

如果对于任意的i，都有occ(u,i)=occ(w,i)，那么我们认为数字串u和w匹配。

例如：(1,2,2,1,3)≈(1,3,2,1,2)

对于一个数字串S和一个正整数k，如果S可以分成若干个长度kk的连续子串，且这些子串两两匹配，那么我们称k是串S的一个完全阿贝尔周期。

给定一个数字串S，请找出它所有的完全阿贝尔周期。

题解：

枚举k，首先k必须是n的约数，然后就能算出每个数字应该出现多少次，O(n)检验即可。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

int ok[maxn],a[maxn],c1[maxn],c2[maxn],n;

bool check(int x)

{

    memset(c1,0,sizeof(c1));

    memset(c2,0,sizeof(c2));

    for(int i=1;i<=x;i++)

        c1[a[i]]++;

    for(int i=2;i<=n/x;i++)

    {

        int l=(i-1)*(x)+1;

        int r=i*(x);

        for(int j=l;j<=r;j++)

        {

            c2[a[j]]++;

            if(c2[a[j]]>c1[a[j]])return 0;

        }

        for(int j=l;j<=r;j++)

            c2[a[j]]--;

    }

    return 1;

}

void solve()

{

    scanf("%d",&n);

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

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

    memset(ok,0,sizeof(ok));

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

    {

        if(n%i==0&&!ok[i])

        {

            if(check(i))

            {

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

                    if(n%j==0)

                        ok[j]=1;

            }

        }

    }

    int fi=0;

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

    {

        if(ok[i])

        {

            if(fi==0)printf("%d",i),fi=1;

            else printf(" %d",i);

        }

    }

    printf("\n");

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)solve();

    return 0;

}

occ

HDU 5908 Abelian Period 暴力