题目描述
给定一颗 \(n\) 个节点的完全二叉树，每个点有权值 \(a_i \in [1,m]\)，定义从 \(i\) 到 \(j\) 的路径的权值 \(s_{i,j}\) 为路径上的最大点权。
求所有树（\(n^m\) 种点权）的 \(\sum_{i=1}^n \sum_{j=i}^n s_{i,j}\) 的和，模 \(998244353\)。
\(1 \leq n \leq 10^{18},1 \leq m \leq 10^5\) 。
算法概述
对于这种全局多情况统计问题，考虑用期望转化，我们发现，一条路径的期望最大值贡献只和这条路径的长度有关，我们枚举最大值 \(j\) ，最大值小于等于 \(j\) 的总情况数是 \(j^{len}\) ，小于等于 \(j - 1\) 的情况是 \((j - 1)^{len}\) 。所以期望最大值是：
最后算出来一条路径的贡献就是：
此处 \(len\) 是边数。
考虑 \(dp\) 求出完全二叉树内有多少条长度为 \(len\) 的路径，首先从满二叉树开始，假设 \(f_{i,j}\) 为深度为 \(i\) 树中有多少长度为 \(j\) 的路径， \(g_{i,j}\) 同理，但是 \(g\) 的路径从根开始。
这样 \(g\) 可以单独计数：\(g_{i,j} = 2g_{i - 1,j - 1}\) ，\(g_{i,0} = 1\) 。
考虑转移 \(f\) ，我们讨论路径是否从根开始，以及是否经过根：
我们就得到了满二叉树的答案。
由于我们知道完全二叉树可以被拆成若干个满二叉树，我们递归进行以下过程，我们检查当前点的数量判断最底层从左往右是否超过了中点，如果超过，左边就是一个深度为 \(dep - 1\)的满二叉树，否则右边就是一个深度为 \(dep - 2\) 的满二叉树。每次将子树答案按照上述 \(f,g\) 合并即可，但是不能单独乘 \(2\) ，要将左右答案加起来。
预处理状态数 \(\Theta(\log^2n)\) ，转移 \(\Theta(\log n)\) ，总复杂度 \(\Theta(\log^3n)\) 。
统计答案时有快速幂，复杂度 \(\Theta(m\log^2n)\) ，考虑长度一定时乘积的指数相同，可以用素数筛优化到 \(\Theta(m\log n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353,N = 205,M = 1e5 + 5;
typedef long long ll;
ll g[N][N],f[N][N],n,m,pw2[N],dp1[N][N],dp2[N][N],E[N];
inline ll ksm(ll base,ll pts)
{
if(pts < 0) return 0;
ll ret = 1;
for(;pts > 0;pts >>= 1,base = base * base % MOD)
if(pts & 1)
ret = ret * base % MOD;
return ret;
}
inline void init()//一个点深度为 1
{
g[1][0] = 1;
for(int i = 2;i <= 128;i++)
{
g[i][0] = 1;
for(int j = 1;j <= 128;j++)
g[i][j] = 2ll * g[i - 1][j - 1] % MOD;
}
f[1][0] = 1;
for(int i = 2;i <= 128;i++)
{
f[i][0] = (ksm(2,i) - 1 + MOD) % MOD;
for(int j = 1;j <= 128;j++)
{
f[i][j] = (g[i][j] + 2ll * f[i - 1][j] % MOD) % MOD;
for(int k = 0;k <= j - 2;k++)
f[i][j] = (f[i][j] + g[i - 1][k] * g[i - 1][j - k - 2] % MOD) % MOD;
}
}
pw2[0] = 1;
for(int i = 1;i <= 62;i++) pw2[i] = pw2[i - 1] * 2ll;
}
inline void dfs(int dep,ll x)
{
if(!x) return;
ll mid = pw2[dep - 1] - 1 + pw2[dep - 2];
int rt;
if(x <= mid) rt = dep - 2,dfs(dep - 1,x - pw2[dep - 2]);
else rt = dep - 1,dfs(dep - 1,x - pw2[dep - 1]);
dp1[dep][0] = (1 + dp1[dep - 1][0] + f[rt][0]) % MOD;
dp2[dep][0] = 1;
for(int i = 1;i <= 128;i++)
dp2[dep][i] = (g[rt][i - 1] + dp2[dep - 1][i - 1]) % MOD;
for(int i = 1;i <= 128;i++)
{
dp1[dep][i] = (dp2[dep][i] + dp1[dep - 1][i] + f[rt][i]) % MOD;
for(int k = 0;k <= i - 2;k++) dp1[dep][i] = (dp1[dep][i] + g[rt][k] * dp2[dep - 1][i - 2 - k] % MOD) % MOD;
}
}
ll pwj[M];
int prime[M],tot = 0,vis[M];
inline void oper(int x,int y)
{
tot = 0;
fill(vis + 1,vis + y + 1,0); pwj[1] = 1;
for(int i = 2;i <= y;i++)
{
if(!vis[i]){prime[++tot] = i;pwj[i] = ksm(i,x);}
for(int j = 1;j <= tot && 1ll * prime[j] * i <= y;j++)
{
vis[i * prime[j]] = 1;
pwj[i * prime[j]] = pwj[i] * pwj[prime[j]] % MOD;
if(!(i % prime[j])) break;
}
}
}
int main()
{
// freopen("c.txt","r",stdin);
init();
int T;
cin>>T;
while(T--)
{
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
memset(E,0,sizeof(E));
cin>>n>>m;
int dep = 1;
while(pw2[dep] - 1 < n) ++dep;
dfs(dep,n);
// cout<<dp1[dep][0]<<" "<<dp1[dep][1]<<" "<<dp1[dep][2]<<endl;
for(int i = 1;i <= 128;i++) //点数
{
oper(i,m);
for(int j = 1;j <= m;j++)
E[i] = (E[i] + j * (pwj[j] - pwj[j - 1] + MOD) % MOD) % MOD;
E[i] = E[i] * ksm(m,n - i) % MOD;
}
ll ans = 0;
for(int i = 0;i <= 127;i++) ans = (ans + dp1[dep][i] * E[i + 1] % MOD) % MOD;
cout<<ans<<endl;
}
return 0;
}
虽然这道题最终没有用期望，但是用期望计算此类全局计数问题通常是一种好方法。