「Codeforces 1034C」Region Separation
没有思维能力了
题意
给你一棵 \(n\) 个点的树,有点权\(a_1,..,a_n\),整棵树是一个1级区域
除非 \(i\) 是最后一个等级,否则每一个
i级区域
都要被分成至少两个i+1级区域
每个点必须恰好属于一个每种等级的区域
一个区域必须是连通的
每个相同等级的区域必须拥有相同的点权和
求有多少种不同的划分方案,模 \(10^9+7\)
\(n\le 10^6,a_i\le 10^9\)
做法
先考虑能不能把整棵树划分为\(k\)个2级区域
令 \(sum=\sum_{i=1}^n a_i\)
每个2级区域
的权值和必然是 \(\frac{sum}{k}\)
有一种显然的判断方式,自底向上找到权值和恰好等于 \(\frac{sum}{k}\) 的子树并割开,若都能满足,则 \(k\) 是合法的
定义 \(s_i\) 表示点 \(i\) 的子树权值和,可以发现上述过程割开的点的 \(s_i\) 都是 \(\frac{sum}{k}\) 的倍数,即 \(s_i \equiv 0\pmod{\frac{sum}{k}}\)
显然 \(k\) 合法当且仅当满足 \(s_i \equiv 0\pmod{\frac{sum}{k}}\) 的点 \(i\) 恰有 \(k\) 个
并且有 \(1 \le k \le n\)
我们考虑一个点 \(i\) 会对哪些 \(k\) 产生贡献
设 \(s_i=\frac{sum}{k} * a\),其中 \(a\) 是整数,即 \(k=\frac{sum}{s_i} * a\)
可以发现合法的 \(k\) 恰好是 \(\frac{sum}{\gcd(sum,s_i)}\) 的倍数
可以记下来之后 \(\mathcal O(n\ln n)\) 地枚举倍数处理
接下来考虑dp
令 \(f_i\) 表示最后一级分成 \(i\) 个区域的方案数
对于合法的 \(k\),有 \(f_k=\sum_{d\mid k,d\ne k} f_d\)
预处理约数即可
总复杂度 \(\mathcal O(n(\log n + \log sum))\)
代码
1 |
|
「Codeforces 1034C」Region Separation
https://cekavis.github.io/codeforces-1034c-region-separation/