bestcoder #88 || hdu 5908 Abelian Period(暴力)
题意：一段数字串，如果一个数字k满足，将该串分成若干个长度为K的子串，这些子串两两满足每个字符出现的次数一样多，那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。
思路：
* 首先我们发现，所有的阿贝尔周期一定是数字串长度（设为n)的因数。
* 然后我们还发现。。。如果某个因子是阿贝尔周期，那么该因子的整数倍中恰好也是n的因子的也一定是阿贝尔周期，类似筛法。
* 然后我们还发现。。。最小的阿贝尔周期一定比数字串中的元素个数大。。。
然而其实后面两个不管也可以过吧。。。因为有点忘了n的约数个数的上界了。。。。
还是太保守了。。。
不过hack了四发哈哈哈。。。要是大号的话今天就紫了呜呜呜
1/* ***********************************************
2Author :111qqz
3Created Time :2016年10月01日 星期六 18时58分00秒
4File Name :code/bc/#88/1002.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E5+7;
33int n;
34vector <int>factor;
35int cnt[N];
36set<int>se;
37bool vis[N];
38int a[N];
39set<int>ans;
40bool solve(int st,int en)
41{
42 bool ret = true;
43 for ( int i = st ; i <= en ; i++)
44 {
45 cnt[a[i]]--;
46 if (cnt[a[i]]<0) ret = false;
47 }
48 for ( int i = st ; i <= en ; i++) cnt[a[i]]++;
49 return ret;
50}
51int main()
52{
53 #ifndef ONLINE_JUDGE
54 freopen("code/in.txt","r",stdin);
55 #endif
56 int T;
57 cin>>T;
58 while (T--)
59 {
60 factor.clear();
61 se.clear();
62 ans.clear();
63 ms(vis,false);
64 scanf("%d",&n);
65 for ( int i = 1 ; i <= n ; i++)
66 {
67 scanf("%d",a+i);
68 se.insert(a[i]);
69 }
70 for ( int i = 1 ; i*i<= n ; i++)
71 {
72 if (n%i==0)
73 {
74 factor.push_back(i);
75 if (i!=n/i) factor.push_back(n/i);
76 }
77 }
78 int fac_siz = factor.size();
79 int fst;
80 for ( int i = 0 ; i < fac_siz ; i++)
81 {
82 if (factor[i]>=int(se.size()))
83 {
84 fst = i;
85 break;
86 }
87 }
88 // cout<<"fst:"<<fst<<endl;
89 for ( int i = fst ; i < fac_siz; i++)
90 {
91 int v = factor[i];
92 if (vis[v]) continue;
93 bool ok = true;
94 ms(cnt,0);
95 for ( int j = 1 ; j <= v ; j++) cnt[a[j]]++;
96 for ( int j = v+1 ; j+v-1 <= n ; j+=v)
97 {
98 if (!solve(j,j+v-1))
99 {
100 ok = false;
101 break;
102 }
103 }
104 if (ok)
105 {
106 for ( int j = i ; j < fac_siz ; j++)
107 {
108 int u = factor[j];
109 if (u%v==0)
110 {
111 ans.insert(u);
112 vis[u] = true;
113 }
114 }
115 }
116 }
117 vector<int> anss;
118 anss.clear();
119 for ( auto it = ans.begin() ; it !=ans.end() ; it++) anss.push_back(*it);
120 int siz = anss.size();
121 for ( int i = 0 ; i < siz-1; i++) printf("%d ",anss[i]);
122 printf("%d\n",anss[siz-1]);
123 }
124 #ifndef ONLINE_JUDGE
125 fclose(stdin);
126 #endif
127 return 0;
128}