【JZOJ4888】【NOIP2016提高A组集训第14场11.12】最近公共祖先

题目描述

YJC最近在学习树的有关知识。今天，他遇到了这么一个概念：最近公共祖先。对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。YJC很聪明，他很快就学会了如何求最近公共祖先。他现在想寻找最近公共祖先有什么性质，于是他提出了这样的一个问题：n层的满k叉树T，求对于每一对(i,j)(1≤i,j≤T的点数)，LCA(T,i,j)的深度的和是多少。这个数字n层的满k叉树指一棵带标号的有根树，深度为i(0≤i

数据范围

​对于30%的数据，满足2≤n,k≤8；

对于50%的数据，满足2≤n,k≤1000000；

对于100%的数据，满足2≤n,k≤998244351。

解法

设f[i]表示贡献为i的点对的个数，那么对于一棵n层k叉树：

f[i]=(kn−i−1k−1)2−k∗(kn−i−1−1k−1)2

则

ans=∑i=1n−1i∗ki∗f[i]=∑i=1n−1i∗ki∗((kn−i−1k−1)2−k∗(kn−i−1−1k−1)2)=k2n∗(∑n−1i∗1i∗k−i)−k2n−1∗(∑n−1i∗1i∗k−i)+(1−k)∗(∑n−1i=1i∗ki)(k−1)2

详细推的过程看图：

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="lca.in";

const char* fout="lca.out";

const ll inf=0x7fffffff;

const ll mo=998244353;

ll n,m,i,j;

ll ans,tmp,tmd;

ll qpower(ll a,ll b){

    ll c=1;

    while (b){

        if (b&1) c=c*a%mo;

        a=a*a%mo;

        b>>=1;

    }

    return c;

}

ll N(ll a){

    return qpower(a,mo-2);

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    cin>>n>>m;

    tmp=((n*(qpower(m,n)-1)%mo*N(m-1)%mo-((qpower(m,n+1)-1)*N(m-1)%mo-n-1)*N(m-1)%mo)%mo+mo)%mo;

    tmd=(n*(qpower(m,n)-1)%mo*N(m-1)%mo-n-tmp)%mo*N(qpower(m,n))%mo;

    ans=N(sqr(m-1)%mo)*(qpower(m,2*n)*tmd%mo-qpower(m,2*n-1)*tmd%mo+(1-m)*tmp%mo)%mo;

    ans=(ans%mo+mo)%mo;

    cout<<ans<<endl;

    return 0;

}

启发

往死里推，正难则反。