[题解] Tree IV
60~70%
可以直接对整棵树进行Dfs，即从根结点1号点开始，若当前结点为，则递归搜索两个子结点
、
，然后暴力计算答案，时间复杂度为
，根据语言选择的不同可能会有不同的得分。
100%
本题利用了两个性质，同时这也是完全二叉树最常用的两个性质：
- 若父结点为
，则其两个子结点分别为
、
- 每一层均有
个结点
可以枚举深度，同时维护每一层结点的范围，分别记作和
，此时，这一层答案为
，然后求和即可。
注意到此题需要对进行取模，所以我们需要预处理出
对
的逆元，按照上述方法进行计算即可。
时间复杂度
参考代码：
class Solution {
public:
typedef long long ll;
const ll mod = 998244353;
inline ll qpow(ll a, ll b) {
ll ret = 1;
while (b) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod, b >>= 1;
}
return ret % mod;
}
long long tree4(long long n) {
ll ans = 0, inv2 = qpow(2, mod - 2), l, r, dep;
for (l = 1, r = 1, dep = 1; r <= n; ++dep) {
ans = (ans + dep * ((l + r) % mod * (r - l + 1) % mod * inv2 % mod) % mod) % mod;
l = r + 1, r = (r + 1) * 2 - 1;
}
ans = (ans + dep * ((l + n) % mod * (n - l + 1) % mod * inv2 % mod) % mod) % mod;
return ans;
}
}; 有关逆元的使用方法，可以自行搜索学习，这里仅提供一个简单的解释：
在除法运算下，除以一个数字后进行取模，等价于乘以这个数字对模数的逆元然后再取模。
查看21道真题和解析
投递华为等公司10个岗位 >