$\LARGE{\textrm{A.三个数}}$

对于一个数 $w$ ，每一次选择 $\left \lceil \frac{w}{2} \right \rceil$ ，要求范围从 $[1, w]$ 变为 $[1, \left \lceil \frac{w}{2} \right \rceil]$ 。

当 $w \leq 3$ 时，选取 ${0, 1, 2}$ 。

时间复杂度 $O(T\log w)$ 。

$\large{\textrm{Code}}$

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

int dfs(long long w) {
    if (w <= 3) return 3;
    return dfs((w + 1) / 2) + 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- ) {
        long long w;
        scanf("%lld", &w);
        printf("%d\n", dfs(w));
    }                  
    return 0;
}

$\LARGE{\textrm{B.一些数}}$

$*$ 若没有填数（$q=0$），则答案为 $Ans = n (n - 2) + 1$

$*$ 定义已填入的数中，数值与编号相差不超过 $1$ 的为合法，否则为不合法

$*$ 若不合法的数量超过 $1$ ，则无解。

$*$ 若同时存在 $x_i = y_i + 1$ 和 $x_i = y_i - 1$ ，个数均为 $1$ ，位置相邻且不存在不合法，那么相当于交换两个数，方案数为 $1$ 。

$*$ 否则若同时存在 $x_i = y_i + 1$ 和 $x_i = y_i - 1$ ，也无解。

$*$ 如果存在一个不合法的位置，唯一方案为将 $y_i$ 调到 $x_i$ 的位置，判断是否可行即可。

$*$ 如果不存在不合法的，那么格式为两边 $x_i = y_i$ ，中间一段为 $x_i = y_i \pm 1$ ，$Ans$ 为中间一段两端的空隙处。

$\large{\textrm{Code}}$

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

long long G(int n) {
    if (n <= 1) return 0;
    return 1ll * n * (n - 2) + 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- ) {
        int n, q, cnt = 0, p = -1;
        int pa = 0, pb = 0, ppa = -1, ppb = -1;
        scanf("%d%d", &n, &q);
        vector<int> g(n + 1, -1), h;
        for (int i = 1; i <= q; i ++ ) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a] = b;
            if (b != a && b != a + 1 && b != a - 1) cnt ++, p = a;
            else h.push_back(a);
            if (a + 1 == g[a]) pa ++ , ppa = a;
            if (a - 1 == g[a]) pb ++ , ppb = a;
        }       
        if (q == 0) {
            printf("%lld\n", 1ll * n * (n - 2) + 1);
            continue;
        }
        if (pa && pb) {
            if (pa == 1 && pb == 1 && abs(ppa - ppb) == 1 && cnt == 0) puts("1");
            else puts("0");
            continue;
        }
        if (cnt > 1) puts("0");
        else if (p != -1) {
            int ans = 1;
            for (int a : h) {
                if (a == p) continue;
                else {
                    if (a == g[a]) {
                        if (a >= min(p, g[p]) && a <= max(p, g[p])) ans = 0;
                    } else if (a - 1 == g[a]) {
                        if (a <= p || a > g[p]) ans = 0;
                    } else if (a + 1 == g[a]) {
                        if (a < g[p] || a >= p) ans = 0;
                    }
                }
            }
            printf("%d\n", ans);
        } else {
            int l = -1, r = h.size();
            for (int i = 0; i < h.size(); i ++ )
                if (g[h[i]] == h[i])
                    l = i;
                else break;
            for (int i = h.size() - 1; i >= 0; i -- )
                if (g[h[i]] == h[i])
                    r = i;
                else break;
            if (r == 0) {
                long long ans = G(h[0] - 1) + G(n - h[h.size() - 1]);
                for (int i = 1; i < h.size(); i ++ )
                    ans += G(h[i] - h[i - 1] - 1);
                printf("%lld\n", ans);
            } else {
                bool KKK_FLAG = false;
                for (int i = l + 1; i <= r - 1; i ++ )
                    if (g[h[i]] - h[i] != g[h[l + 1]] - h[l + 1])
                        KKK_FLAG = true;
                if (KKK_FLAG) puts("0");
                else {
                    int A, B;
                    if (l == -1) A = h[0] - 1;
                    else A = h[l + 1] - h[l] - 1;
                    if (r == h.size()) B = n - h[h.size() - 1];
                    else B = h[r] - h[r - 1] - 1;
                    if (pa) A ++ ;
                    if (pb) B ++ ;
                    printf("%lld\n", 1ll * A * B);
                }
            }
        }
    }                  
    return 0;
}

$\LARGE{\textrm{C.一颗树}}$

先以 $1$ 为根。

$len_i$ 表示 $a_i$ 的长度，$siz_i$ 表示以 $i$ 为根的子树大小。

设 $f_i$ 表示从 $i$ 的子树到 $i$ 的路径权值之和。

设 $g_i$ 表示以 $i$ 结尾的路径权值之和。

先由递推公式

$$f_i = siz_i \times a_i + \sum_{j \in son_i} f_j \times 10^{len_i}$$

求 $f_i$ 。

得 $g_1 = f_1$ ，由 $g_i$ 即可推出所有与 $i$ 相邻的点的 $g$ 。

$$g_j = f_j + \left ( g_i - n \times a_i - f_j \times 10^{len_i} + a_i \times (siz_i - siz_j)\right) \times 10^{len_j} + a_j \times (siz_1 - siz_j)$$

时间复杂度 $O(n)$ 。

$\large{\textrm{Cpde}}$

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

const int N = 1e6 + 10, P = 998244353;
int n;
int a[N], fa[N], c[N], siz[N], len[N], base[30];
int h[N], e[N * 2], ne[N * 2], idx;
int f[N], g[N];

void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++ ;
}

int calc(int x) {
    if (!x) return 1;
    int r = 0;
    while (x) x /= 10, r ++ ;
    return r;
}

int qpow(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = 1ll * r * a % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return r;
}

void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u]) continue;
        int tmp = 1ll * (1ll * (g[u] + P - 1ll * a[u] * n % P) % P * qpow(base[len[u]], P - 2) % P + P - f[j]) % P * base[len[u]] % P + 1ll * a[u] * (siz[1] - siz[j]) % P;
        g[j] = (f[j] + 1ll * tmp * base[len[j]] % P + 1ll * (siz[1] - siz[j]) * a[j] % P) % P;
        dfs(j);
    }
}

int main()
{
    base[0] = 1;
    for (int i = 1; i <= 20; i ++ ) base[i] = 1ll * base[i - 1] * 10 % P;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), len[i] = calc(a[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        scanf("%d", &fa[i + 1]);
        add(fa[i + 1], i + 1), add(i + 1, fa[i + 1]);
        c[fa[i + 1]] ++ , c[i + 1] ++ ;
    }
    for (int i = n; i >= 1; i -- ) {
        siz[i] = 1;
        for (int j = h[i]; ~j; j = ne[j]) 
            if (e[j] != fa[i])
                siz[i] += siz[e[j]], f[i] = (f[i] + 1ll * f[e[j]] * base[len[i]] % P) % P;
        f[i] = (f[i] + 1ll * siz[i] * a[i] % P) % P;
    }
    g[1] = f[1];
    dfs(1);
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) ans = (ans + g[i]) % P;
    printf("%d\n", ans);
    return 0;
}

$\LARGE{\textrm{D.好多数}}$

对于 $x$ 进行质因式分解，设分解后第 $i$ 个因数的指数相差 $t_i$ 。

若 $x$ 不是 $n$ 的因数，则输出 $0$ 。

设 $f_i$ 为 $n$ 变换恰好 $i$ 次的方案数，根据插板法，

$f_i = \prod_j \left ( ^{t_j + i - 1}_{\ \ \ i - 1} \right )$

由于每一次可能都不除，所以减掉 $$\sum_{j=1}^{i-1} \left( ^{i}_{j} \right) f_j$$

即

$$f_i = \prod_j \left ( ^{t_j + i - 1}_{\ \ \ i - 1} \right) - \sum_{j=1}^{i-1} \left( ^{i}_{j} \right) f_j$$

$\large{\textrm{Code}}$

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

const int N = 10010, P = 998244353;
int mul[N], inv[N], a[N], b[N];
int dp[N];

int qpow(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = 1ll * r * a % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return r;
}

int C(int a, int b) {
    return 1ll * mul[a] * inv[a - b] % P * inv[b] % P;
}

int main()
{
    mul[0] = inv[0] = 1;
    for (int i = 1; i <= 10000; i ++ ) mul[i] = 1ll * mul[i - 1] * i % P;
    inv[10000] = qpow(mul[10000], P - 2);
    for (int i = 9999; i >= 1; i -- ) inv[i] = 1ll * inv[i + 1] * (i + 1) % P;
    int n, q;
    for (n = 1; ; n ++ ) {
        scanf("%d%d", &a[n], &b[n]);
        if (!a[n]) {n -- ; break;}
    }
    scanf("%d", &q);
    while (q -- ) {
        long long x, m = 0;
        scanf("%lld", &x);
        if (x == 1) {printf("0 "); continue;}
        vector<int> t(n + 1);
        for (int i = 1; i <= n; i ++ ) {
            t[i] = b[i];
            while (x % a[i] == 0) x /= a[i], t[i] -- ;
            m += t[i];
        }
        if (x > 1) {printf("0 "); continue;}
        if (m == 0) {printf("1 "); continue;}
        int ans = 0;
        for (int i = 1; i <= m; i ++ ) {
            dp[i] = 1;
            for (int j = 1; j <= n; j ++ )
                dp[i] = 1ll * dp[i] * C(t[j] + i - 1, i - 1) % P;
            for (int j = 1; j < i; j ++ ) dp[i] = (dp[i] + P - 1ll * C(i, j) * dp[j] % P) % P;
            ans = (ans + dp[i]) % P;
        }
        printf("%d ", ans);
    }
    return 0;
}