0%

「Codeforces #1034C」Region Separation

没有思维能力了

Codeforces #1034C

题意

给你一棵 $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
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
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}

const int N = 1000005, P = 1000000007;
int ans, n, a[N], fa[N], f[N], g[N];
ll sum, s[N];
vector<int> d[N];
inline ll gcd(ll x, ll y){ return y?gcd(y, x%y):x;}
int main() {
read(n);
for(int i=1; i<=n; ++i) read(a[i]), sum+=a[i];
for(int i=2; i<=n; ++i) read(fa[i]);
for(int i=n; i; --i){
s[i]+=a[i], s[fa[i]]+=s[i];
ll x=sum/gcd(sum, s[i]);
if(x<=n) ++f[x];
}
for(int i=n; i; --i) for(int j=i<<1; j<=n; j+=i) f[j]+=f[i], d[j].push_back(i);
ans=g[1]=1;
for(int i=2; i<=n; ++i) if(f[i]==i){
for(int j:d[i]) (g[i]+=g[j])%=P;
(ans+=g[i])%=P;
}
return printf("%d", ans), 0;
}