洛谷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 种状态下的方案，需要按照顺序依次输出。

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

之后若干行，每行 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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！