【jzoj4888】【最近公共祖先】

題目大意

n層的滿k叉樹T，求對于每一對(i,j)(1≤i,j≤T的點數)，LCA(T,i,j)的深度的和是多少。這個數字n層的滿k叉樹指一棵帶标号的有根樹，深度為i(0≤i

解題思路

顯然得出 ans=∑n−1i=1i∗ki∗(((kn−i−1)/(k−1))2−k∗((kn−i−1−1)/(k−1))2)

化簡得 ans=(k2n−kn+1+kn−k)/(k−1)3−(2n−2)∗kn/(k−1)2

具體化簡方法不多說，大概思路是使用等比數列求和，以及錯位相消法。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
LL const mod=998244353;
LL n,k;
LL Pow(LL x,LL y){
    LL z=1;
    for(;y;){
        if(y%2)z=(z*x)%mod;
        x=(x*x)%mod;
        y/=2;
    }
    return z;
}
int main(){
    freopen("lca.in","r",stdin);
    freopen("lca.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    printf("%lld",((((Pow(k,2*n)-Pow(k,n+1)+Pow(k,n)-k)%mod+mod)%mod*Pow(k-1,mod-2)%mod-(2*n-2)*Pow(k,n)%mod)%mod+mod)%mod*Pow(k-1,mod-2)%mod*Pow(k-1,mod-2)%mod);
    return 0;
}