洛谷P2351 吊灯

题目背景
山东省省队选拔赛第二试（第一天）

题目描述
Alice 家里有一盏很大的吊灯。所谓吊灯，就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的，剩下的灯泡都是挂在其他的灯泡上的。也就是说，整个吊灯实际上类似于一棵树。其中编号为 11 的灯泡是挂在天花板上的，剩下的灯泡都是挂在编号小于自己的灯泡上的。

现在，Alice 想要办一场派对，她想改造一下这盏吊灯，将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的，并且每一种颜色的灯泡个数都是相同的。

Alice 希望你能告诉她，总共有哪些方案。

Alice 是一个贪心的孩子，如果她发现方案不够多，或者太多了，就会很不高兴，于是她会尝试调整。对于编号为 xx（x\neq 1x

=1）的灯泡，如果原来是挂在编号为 f_xf
x
​
的灯泡上，那么 Alice 会把第 xx 个灯泡挂到第 (f_x + 19940105)\bmod (x-1) + 1(f
x
​
+19940105)mod(x−1)+1 个灯泡上。

由于九在古汉语中表示极大的数，于是，Alice 决定只调整 99 次。对于原始状态和每一次调整过的状态，Alice 希望你依次告诉她每种状态下有哪些方案。

输入格式
第一行一个整数 nn，表示灯泡的数量。

接下来一行，有 n-1n−1 个整数 U_iU
i
​
，第 ii 个数表示第 i+1i+1 个灯泡挂在了第 U_iU
i
​
个的下面。保证编号为 11 的灯泡是挂在天花板上的。数字之间用逗号（西文标点）, 隔开且最后一个数字后面没有逗号。

输出格式
对于 1010 种状态下的方案，需要按照顺序依次输出。

对于每一种状态，需要先输出单独的一行，表示状态编号，如样例所示。

洛谷153道题目代码

rar 0星 超过10%的资源 33KB

下载

之后若干行，每行 11 个整数，表示划分方案中每种颜色的灯泡个数。

按升序输出。

输入输出样例
输入 #1复制
6
1,2,3,4,5
输出 #1复制
Case #1:
1
2
3
6
Case #2:
1
2
6
Case #3:
1
3
6
Case #4:
1
3
6
Case #5:
1
3
6
Case #6:
1
2
6
Case #7:
1
2
3
6
Case #8:
1
6
Case #9:
1
2
6
Case #10:
1
3
6
说明/提示
对于 20%20% 的数据，n\leq 3\times 10^3n≤3×10
3
。

对于 40%40% 的数据，n\leq 5\times 10^4n≤5×10
4
。

对于 50%50% 的数据，n\leq 10^5n≤10
5
。

对于 60%60% 的数据，n\leq 3\times 10^5n≤3×10
5
。

对于 70%70% 的数据，n\leq 7\times 10^5n≤7×10
5
。

对于 100%100% 的数据，1\leq n\leq 1.2\times 10^61≤n≤1.2×10
6
。
上代码：

#include
using namespace std;
inline void read(int &x){
    char c=getchar();
    int p=1;
    x=0;
    while(!isdigit(c)){
        if(c=='-')p=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x*=p;
}
const int maxn=2000005;
int tot,f[maxn],n,cnt[maxn],s[maxn];
vector<int>vec,ans;
int main(){
    read(n);
    for(register int i=2;i<=n;++i){
        read(f[i]);
    }
    for(register int i=1;i<=n;++i){
        if(n%i==0)vec.push_back(i);
    }
    int sum=vec.size()-1;
    for(register int cas=1;cas<=10;++cas){
        printf("Case #%d:\n",cas);
        ans.clear();
        for(register int i=1;i<=n;++i){
            s[i]=1;
        }
        for(register int i=n;i>1;--i){
            s[f[i]]+=s[i];
        }
        memset(cnt,0,sizeof(cnt));
        for(register int i=1;i<=n;++i){
            cnt[s[i]]++;
        }
        ans.push_back(1);
        for(register int i=1;i<=sum;++i){
            tot=0;
            for(register int j=vec[i];j<=n;j+=vec[i]){
                tot+=cnt[j];
            }
            if(tot>=n/vec[i])ans.push_back(vec[i]);
        }
        for(register int i=0;i<ans.size();++i){
            printf("%d\n",ans[i]);
        }
        for(register int i=2;i<=n;++i){
            f[i]=(f[i]+19940105)%(i-1)+1;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58