menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[调和级数+DP]Codeforces1047E【Region Separation】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论

题目概述

有一棵树,现在要把树分成若干个级别,每个级别是若干个权值加和相等的连通块。第一个级别是所有节点,之后的级别需要满足第 $i$ 个级别中的连通块均在 $i-1$ 中连通且 $i$ 的块数必须小于 $i-1$ 。问总方案数。

解题报告

好题。假设所有点的权值和是 $S$ ,首先先分析分成 $k$ 个连通块需要满足的条件,可以发现肯定是从包含叶子且子树权值和为 $S\over k$ 的节点开始删除,重复这个过程 $k$ 次就可以判断 $k$ 是否满足。

实际上就是找 ${S\over k}|sum_x$ 的 $x$ 的个数是不是刚好为 $k$ ,如果是的,那么肯定可以从最下面的开始删除,然后逐步删除上面的。通过 $S\over(sum_x,S)$ 可以得出对于 $x$ 的最小满足的 $k$ ,通过调和级数就可以算出所有 $k$ 的出现个数。

把满足的 $k$ 都拿出来排序,那么问题变成了这样:有多少个子序列满足后一项是前一项的倍数,直接DP。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;

int n,w[maxn+5],fa[maxn+5],f[maxn+5],ans[maxn+5];LL sum[maxn+5];

LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
inline void AMOD (int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&w[i]),sum[i]=w[i];
    for (int i=2;i<=n;i++) scanf("%d",&fa[i]);for (int i=n;i>1;i--) sum[fa[i]]+=sum[i];
    f[1]++;for (int i=2;i<=n;i++) if ((sum[i]=sum[1]/gcd(sum[1],sum[i]))<=n) f[sum[i]]++;
    for (int i=n;i;i--) for (int j=i<<1;j<=n;j+=i) f[j]+=f[i];
    for (int i=n;i;i--) if (f[i]==i) {ans[i]=1;for (int j=i<<1;j<=n;j+=i) AMOD(ans[i],ans[j]);}
    return printf("%d\n",ans[1]),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up