传送门

Solution

设最大节点数为 MM，因为第 ii 层最多有 26i26^i 个节点，所以有 M=∑i=0mmin{26i,n}M=\sum \limits ^m_{i=0}\min \{26^i,n\}。

对于第 ii 层上的一个节点，一个字符串包含它的概率为 126i\dfrac{1}{26^i}。该节点不存在即为没有字符串包含它，这个事件的概率为 (1−126i)n(1-\dfrac{1}{26^i})^n。因此它对答案的贡献为 1−(1−126i)n1-(1-\dfrac{1}{26^i})^n。这一层共有 26i26^i 个可能的节点，它们对答案的贡献即为 (1−(1−126i)n)26i(1-(1-\dfrac{1}{26^i})^n)26^i。

所以整棵 Trie 树节点数量的期望为

∑i=1m(1−(1−126i)n)26i+1\sum \limits ^m_{i=1}(1-(1-\dfrac{1}{26^i})^n)26^i+1

最后加上的 11 为根节点。

计算 MM 的时候要注意，不要对 26i26^i 直接取模，因为可能 26^i\bmod p < n 导致答案出错。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 998244353;

ll n, m, sum, maxn;

ll fst(ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y = y - a / b * x;
}

int main()
{
    maxn = sum = 1;
    scanf("%lld%lld", &n, &m);
    ll mul = 1;
    for (int i = 1; i <= m; i++) {
        if (mul <= n) mul *= 26;
        maxn = (maxn + min(mul, n) + mod) % mod;
    }
    for (int i = 1; i <= m; i++) {
        ll inv, y, mi = fst(26, i);
        exgcd(mi, mod, inv, y);
        inv = (inv % mod + mod) % mod;
        sum = (sum + (1 - fst(1 - inv, n) + mod) % mod * fst(26, i) % mod) % mod;
    }
    printf("%lld %lld", maxn, sum);
    return 0;
}