DP做题记录（三）（2025.4.5 - 2025.4.19）

· · 算法·理论

P11626 [迷宫寻路 Round 3] 七连击

对于一段区间的划分，很容易想到 DP。

我们设 f_{i, j} 表示把前 i 个数划分成 j 段的答案，再设 g_{i, j} 表示把前 i 个数划分成 j 段的方案数。考虑前一个划分点在什么位置，可以得到：

g_{i, j} = \displaystyle\sum_{k = 1}^{i - 1} g_{k, j - 1}, g_{0, 0} = 1

我们再考虑划分出的这一段对答案的贡献。如果们固定了一段区间 [l, i]，那么这段本身的贡献就是 \gcd(a_l, \dots, a_i)，而 [1, l - 1] 就可以随便划分了，此时：

f_{i, j} = \displaystyle\sum_{k = 1}^{i - 1} f_{k, j - 1} + g_{k, j - 1} \times \gcd_{l = k + 1}^i a_l

观察可以发现，g_{i, j} 的转移为上一行一段前缀的和，可以前缀和优化。而 f_{i, j} 则因为加入了 \gcd 的操作，不是很好前缀和优化。不过我们考虑当固定了右端点 i，左端点 l 不断向左移动的过程中，区间 \gcd 一定是单调不升的，而且每次减小，至少除以了一个 2，那么一定只用 O(\log n) 次就除到了 1，然后就不会变了。于是我们二分答案找到每次区间 \gcd 变化的位置，那么左端点从上一个二分出的点 x 到这一次二分出的点 y 时，区间 \gcd 是不变的，那么此时就可以前缀和优化了。设分了 k 段，复杂度为 O(kn \log^2 n)，足以通过此题。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9, LOGN = 19, MOD = 998244353;
int st[N][LOGN], LOG2[N], a[N], g[N][9], f[N][9], sumg[N][9], sumf[N][9], n;
void build(){
    LOG2[1] = 0;
    for(int i = 2; i <= n; i++)
        LOG2[i] = LOG2[i >> 1] + 1;
    for(int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for(int j = 1; j <= LOG2[n]; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int ask(int l, int r){
    int k = LOG2[r - l + 1];
    return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
int find(int l, int r){
    int val = ask(l, r), res = l, tmp = r;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ask(mid, tmp) == val){
            l = mid + 1;
            res = mid;
        } else
            r = mid - 1;
    }
    return res;
}
signed main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build();
    g[0][0] = sumg[0][0] = 1;
    for(int i = 1; i <= n; i++){
        g[i][0] = 1, sumg[i][0] = 1;
        for(int j = 1; j <= 7; j++){
            g[i][j] = sumg[i - 1][j - 1];
            sumg[i][j] = (sumg[i - 1][j] + g[i][j]) % MOD;
        }   
    }
    for(int i = 1; i <= n; i++){
        f[i][1] = ask(1, i);
        sumf[i][1] = (sumf[i - 1][1] + f[i][1]) % MOD;
        for(int l = 1, r; l <= i; l = r + 1){
            r = find(l, i);
            for(int j = 2; j <= 7; j++){
                if(!f[i][j]) f[i][j] = sumf[i - 1][j - 1];//wa *2
                f[i][j] = (f[i][j] + ask(l, i) * (sumg[r - 1][j - 1] - sumg[l - 2][j - 1] + MOD) % MOD) % MOD;
                sumf[i][j] = (sumf[i - 1][j] + f[i][j]) % MOD;
            }
        }
    }
    printf("%lld", sumf[n][7]);
    return 0;
}

P11173 「CMOI R1」We Want To Run / Nilpotent

套用非常经典的线性代数结论，一张图的邻接矩阵的 k 次方后每个位置 A_{u, v} 就表示 u 到 v 的所有路径中长度为 k 的路径条数。

注意到这张图中左右边权非负，那么在矩乘时，如果两个位置都不为 0，那么乘积也不为 0，必须至少有一个是 0 才可以，于是，每个位置 A_{i, j} 我们不用考虑它的具体取值，只用考虑它是否为 0。

那么现在，A^b = O 的含义就变成了对一个边权只有 0 和 1 的图，找到最小的 b 使得图中没有长度为 b 的链。显然，如果这张图存在环，那么图中就不存在最长链（可以一直在环上绕），因此这张图一定是一个 DAG。

由于我们要统计方案数，因此我们考虑枚举贡献。如果这张图中最长链上的点数为 b，那么说明最长链的长度为 b - 1，于是对答案的贡献就是 b。由于是 DAG 我们可以按拓扑序一层一层枚举。

我们设 dp_{i, j, k} 表示前 i 个点分了 j 层，上一层有 k 个点的方案数。我们先枚举这一层的点数 p，那么这 p 个点就可以从这 i + p 个点中选出，因此转移时首先要乘以 \displaystyle\binom{i + p}{p}。

其次，这一层的点必须至少与上一层的 1 个点连边，边权任意，于是转移时又要乘以 (a^k - 1)^p（减 1 是因为不能一个点都不连）。

最后，这一层的点可以与之前层的点随便连边，之前的点一共有 i - k 个，于是答案又要乘以 a^{p(i - k)}，因此我们就得到了转移方程 dp_{i, j, k} \times \displaystyle\binom{i + p}{p} (a^k - 1)^p a^{p(i - k)} = dp_{i + p, j + 1, p}。那么答案就是 \displaystyle\sum_{j = 1}^n j \sum_{k = 1}^{n - j + 1} dp_{n, j, k}。

我们其实可以发现，j 其实顶没用的（和我一样），只是在最后求答案时要乘以 j。我们考虑 j 的组合意义，就是在这 j 层中选一层作为关键层。这是因为 \displaystyle\binom j1 = j。

现在我们可以改变 DP 的函数了，设 dp_{i, j, 0 / 1} 表示给前 i 个数分层，上一层有 j 个数，且是否选择过关键层的答案，dp_{i, j, 0} 到 dp_{i + p, p, 0}，dp_{i, j, 1} 到 dp_{i + p, p, 1} 直接用之前的转移方程。对于每一层，都可以选择这一层成为关键层，于是把 dp_{i, j, 0} 按照转移方程加到 dp_{i + p, p, 1} 就可以了，复杂度降低到 O(n^3)，足以通过此题。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N = 6e2 + 9, MOD = 202407031;
int dp[N][N][2], binom[N][N], pwr[N * N], po[N][N], n, a, ans;
int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') 
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = ((x << 1) + (x << 3) + (ch ^ 48));
        ch = getchar();
    }
    return x * f;
}
void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
signed main(){
    n = read();
    a = read();
    a %= MOD;
    pwr[0] = 1;
    for(int i = 1; i <= n * n; i++)
        pwr[i] = pwr[i - 1] * a % MOD;
    for(int i = 1; i <= n; i++){
        po[i][0] = 1;
        for(int j = 1; j <= n; j++)
            po[i][j] = po[i][j - 1] * (pwr[i] - 1 + MOD) % MOD;
    }
    binom[0][0] = 1;
    for(int i = 1; i <= n; i++){
        binom[i][0] = 1;
        for(int j = 1; j <= i; j++)
            binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % MOD;
    }
    for(int i = 1; i <= n; i++)
        dp[i][i][1] = dp[i][i][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dp[i][j][0] != 0){
                for(int p = 1; p <= n - i; p++){
                    dp[i + p][p][0] = (dp[i + p][p][0] + dp[i][j][0] * binom[i + p][p] % MOD * po[j][p] % MOD * pwr[p * (i - j)] % MOD) % MOD;
                    dp[i + p][p][1] = (dp[i + p][p][1] + dp[i][j][0] * binom[i + p][p] % MOD * po[j][p] % MOD * pwr[p * (i - j)] % MOD) % MOD;
                }
            }
            if(dp[i][j][1] != 0){
                for(int p = 1; p <= n - i; p++)
                    dp[i + p][p][1] = (dp[i + p][p][1] + dp[i][j][1] * binom[i + p][p] % MOD * po[j][p] % MOD * pwr[p * (i - j)] % MOD) % MOD;
            }   
        }
    }
    for(int i = 1; i <= n; i++)
        ans = (ans + dp[n][i][1]) % MOD;
    write(ans);
    return 0;
}

P11030 『DABOI Round 1』Blessings Repeated

由于 m 小的可怜，我们考虑把 T 这个字符串拆分成若干个子串，分别放入这 k 个重复的 S 中，然后就可以用组合数计算了。

那么问题就转变成了求出 T 的所有字串在 S 中作为子序列的出现次数。我们把 T_{[l, r]} 单独抽出来，设 dp_{i, j} 表示 S 的前 i 个字符中 T_{l, j} 出现的次数，那么如果 S_i = T_j，就可以把 dp_{i - 1, j - 1} 的值加进来，否则就只能赋值为 dp_{i - 1, j}，因此

dp_{i, j} = \begin{cases} dp_{i - 1, j} + dp_{i - 1, j - 1} & S_i = T_j\\ dp_{i - 1, j} & S_i \neq T_j \end{cases}

其中初值为 dp_{0, 0} = 1，可以发现这个式子和背包类似，因此第二维倒序枚举可以除掉 j 这一维。于是我们在时间复杂度为 O(nm^3)，空间复杂度为 O(n) 的情况下求出了 T 的所有字串在 S 中作为子序列的出现次数。

现在就比较好做了，我们将 T 划分成若干个段，设划分了 l 段，那么将这 l 段放入 k 个重复的 S 中就有 \displaystyle\binom kl 种方案，而这些方案的权值是这 l 段分别在 S 中作为子序列的出现次数的积，直接加入到答案中。由于 m 只有 10，这部分的时间复杂度比较小，可以忽略不计，那么我们用 O(nm^3) 的时间复杂度完成了此题。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e3 + 9, M = 19, MOD = 998244353;
int k, dp[N], tim[M][M], inv[M], fac[M], n, m, ans;
char s[N], t[M];
vector <int> vec;
int qpow(int a, int b){
    int res = 1;
    while(b > 0){
        if(b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
int binom(int a, int b){
    if(b > a)
        return 0;
    __int128 res = 1;
    for(int i = a; i >= a - b + 1; i--)
        res = res * i % MOD;
    return res * inv[b] % MOD;
}
void dfs(int now){
    if(now == 0){
        int l = 1, r, tmp = 1;
        for(int i = 0; i < (int)vec.size(); i++){
            r = l + vec[i] - 1;
            tmp = tmp * tim[l][r] % MOD;
            l = r + 1;
        }
        ans = (ans + tmp * binom(k, vec.size()) % MOD) % MOD;
        return;
    }
    for(int i = 1; i <= now; i++){
        vec.push_back(i);
        dfs(now - i);
        vec.pop_back();
    }
}
signed main(){
    scanf("%lld", &k);
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1);
    m = strlen(t + 1);
    fac[0] = 1;
    for(int i = 1; i <= m; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv[m] = qpow(fac[m], MOD - 2);
    for(int i = m - 1; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    for(int l = 1; l <= m; l++){
        for(int r = l; r <= m; r++){
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for(int i = 1; i <= n; i++)
                for(int j = r; j >= l; j--)
                    if(t[j] == s[i])
                        dp[j - l + 1] = (dp[j - l + 1] + dp[j - l]) % MOD;
            tim[l][r] = dp[r - l + 1];
        }
    }
    dfs(m);
    printf("%lld", ans);
    return 0;
}

P10879 「KDOI-07」对树链剖分的爱

我们考虑通常如何把一条树链 (u, v) 增加 w 的权值，最暴力的做法就是把 u 和 v 分别到根的路径上的边权加 w，再将 u 和 v 的 LCA 到根的路径上的边权减 2 \times w。其实可以发现，不管 u 和 v 是否是祖先关系，它们中深度更深的点的父边一定加上了 w。而且这道题目有一个有趣的性质，那就是一个点 u 的父亲一定比 u 的编号小，那也就是 u, v 中编号更大的点的父边一定加上了 w。

推出了性质后，我们从简单情况一步一步分析。假设只有一组修改 (u, v, w)，那么我们直接设 dp_{i, j}(i \geq j) 表示从点对 (u, v) 往上走到 (i, j)(u \leq i, j \leq v)，i 的父边权值的期望，由于推出的性质，只有 i 的父边一定加上了 w，因此可以很轻松写出转移方程，枚举 fa_i \in [l_i, r_i]，那么若 fa_i \geq j，f_{fa_i, j} = \displaystyle\frac{w}{r_i - l_i + 1}；若 fa_i < j，f_{j, fa_i} = \displaystyle\frac{w}{r_i - l_i + 1}。

我们考虑期望的线性性，两个独立事件的期望和，等于这两个事件至少发生一件的期望，那么由于这几个加法操作相互独立，它们的期望可以直接加在一起，于是改变 f_{i, j}(i \geq j) 的含义，为所有能够往上走到 (i, j) 的所有点对 (u, v)，从 (u, v) 往上走到 (i, j)，i 的父边权的期望的和，转移方程几乎不变，只是把赋值变成加操作。此时一个点 u 的答案就是 \displaystyle\sum_{u > v} dp_{v, u}。不过这样时间复杂度是 O(n^3)，还是过不了。

我们考虑转移方程，对于所有 fa_i \geq j，f_{fa_i, j} = \displaystyle\frac{w}{r_i - l_i + 1}，此时 j 是不变的，而 fa_i 在区间 [j, r_i] 中，这相当于是对平面上一个 1 \times (r_i - j + 1) 的矩阵加上了 w；同理，对于所有 fa_i < j，这相当于是对平面上一个 (j - l_i) \times 1 的矩阵加上了 w，由于是把所有操作都执行完后才进行询问，于是可以用二维差分将时间复杂度优化成 O(n^2 + m)，足以通过此题。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e3 + 9, MOD = 998244353;
int f[N][N], s1[N][N], s2[N][N], inv[N], l[N], r[N], ans[N], n, m;
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i++)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}
signed main(){
    init();
    scanf("%lld", &n);
    for(int i = 2; i <= n; i++)
        scanf("%lld%lld", &l[i], &r[i]);
    scanf("%lld", &m);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        if(u < v)
            swap(u, v);
        f[u][v] = (f[u][v] + w) % MOD;
    }
    for(int i = n; i >= 1; i--){
        for(int j = i - 1; j >= 1; j--){
            s1[i][j] = (s1[i][j] + s1[i + 1][j]) % MOD;
            s2[i][j] = (s2[i][j] + s2[i][j + 1]) % MOD;
            f[i][j] = (f[i][j] + s1[i][j] + s2[i][j]) % MOD;
            ans[i] = (ans[i] + f[i][j]) % MOD;
            int num = f[i][j] * inv[r[i] - l[i] + 1] % MOD;
            if(j < l[i]){
                s1[r[i]][j] = (s1[r[i]][j] + num) % MOD;
                s1[l[i] - 1][j] = ((s1[l[i] - 1][j] - num) % MOD + MOD) % MOD;
            } else if(j > r[i]){
                s2[j][r[i]] = (s2[j][r[i]] + num) % MOD;
                s2[j][l[i] - 1] = ((s2[j][l[i] - 1] - num) % MOD + MOD) % MOD;
            } else {
                s2[j][j] = (s2[j][j] + num) % MOD;
                s1[r[i]][j] = (s1[r[i]][j] + num) % MOD;
                s2[j][l[i] - 1] = ((s2[j][l[i] - 1] - num) % MOD + MOD) % MOD;
                s1[j][j] = ((s1[j][j] - num) % MOD + MOD) % MOD;
            }
        }
    }
    for(int i = 2; i <= n; i++)
        printf("%lld ", ans[i]);
    return 0;
}

P10868 [HBCPC2024] Points on the Number Axis B

我们先从简单的情况考虑，如果只有两个点 x_1 和 x_2，那么中点一定是 \displaystyle\frac{x_1}{2} + \frac{x_2}{2}，如果有三个点 x_1, x_2, x_3，那么第一次分两种情况：

因此期望就是 \displaystyle\frac 12 \times (\frac{x_1}{4} + \frac{x_2}{4} + \frac{x_3}{2}) + \frac 12 \times (\frac{x_1}{2} + \frac{x_2}{4} + \frac{x_3}{4}) = \frac 38 x_1 + \frac 14 x_2 + \frac 38 x_3。

其实可以发现，最后的式子一定可以表示成 \displaystyle\sum w_k x_k，可以感性理解一下，每次求中点时，都把两边已经得到的式子乘了一个 \displaystyle\frac 12，这并不会改变式子的次数，只会改变式子的系数，因此我们现在需要求出所有的 w_i。

设 dp_{i, j} 表示当前枚举的点（可能是合并出来的）左边还剩 i 个点，右边还剩 j 个点，中间这个点系数的期望。考虑本次合并，如果是将左边 i 个点中任意两个点合并（一共 i - 1 中合并方法），对当前枚举的这个点的系数没有影响，因此 dp_{i, j} 首先要加上 \displaystyle\frac{i - 1}{i + j}dp_{i - 1, j}（系数表示从 i + j 个可合并位置中选出 i - 1 个位置的概率），同理，dp_{i, j} 也要加上 \displaystyle\frac{j - 1}{i + j} dp_{i, j - 1}。

现在来考虑将枚举到的这个点合并进来，此时就要乘以系数 \displaystyle\frac 12，于是 dp_{i, j} 还要加上 \displaystyle\frac 12 \times \frac{1}{i + j} \times (dp_{i - 1, j} + dp_{i, j - 1})，因此最终的转移方程就是 dp_{i, j} = \displaystyle\frac{i - 1}{i + j} dp_{i - 1, j} + \frac 12 \frac {1}{i + j} dp_{i - 1,j} + \frac 12 \frac{1}{i + j} dp_{i, j - 1} + \frac{j - 1}{i + j} dp_{i, j - 1}。一个点的贡献就是 \displaystyle\sum dp_{i - 1, n - i} x_i

我们现在考虑优化，首先一个优化方式就是将期望改写成总和除以总方案数，那么就可以将转移方程改写为 dp_{i, j} = \displaystyle\frac{1}{(n - 1)!} [(i - \frac 12) dp_{i - 1, j} + (j - \frac 12) dp_{i, j - 1}]。

现在就到了要充分发扬类人智慧的时候了，考虑 dp 式子的组合含义（其实也可以直接矩乘加特征向量做，不过特别难算），那就相当于从 (i, j) 这个点走到 (0, 0)，往上走需要花费 i - \displaystyle\frac 12 的代价，往左走需要花费 j - \displaystyle\frac 12 的代价，所有路径的代价和。那么我们一定走了 i + j 步，其中 i 步向上可以随时走，因此 dp_{i, j} = \displaystyle\binom{i + j}{i} (i - \frac 12)^{\underline{i - 1}} (j - \frac 12)^{\underline{j - 1}}。此时我们只需要预处理一下就可以 O(n) 通过此题了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9, MOD = 998244353;
int x[N], fac[N], inv[N], des[N], c, n, ans;
int qpow(int a, int b){
    int res = 1;
    while(b > 0){
        if(b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
signed main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &x[i]);
    c = qpow(2, MOD - 2);
    fac[0] = 1;
    for(int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv[n] = qpow(fac[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    des[0] = 1;
    for(int i = 1; i <= n; i++)
        des[i] = (i - c + MOD) % MOD * des[i - 1] % MOD;
    for(int i = 1; i <= n; i++)
        ans = (ans + x[i] * des[i - 1] % MOD * des[n - i] % MOD * inv[i - 1] % MOD * inv[n - i] % MOD) % MOD;
    printf("%lld", ans);
    return 0;
}

P9428 [蓝桥杯 2023 国 B] 逃跑

这道题代码难度只有红，但思维难度直接把这道题提升到了绿。

我们设 dp_i 表示从第 i 个星球出发到根节点花费的最短时间的期望。

显然，如果一个星球 v 的父亲节点 u 是跳板星球，那么直接跳跃与往上走父亲是一样的效果，因此 dp_v = dp_u + 1。

那么如果 v 的父亲节点 u 不是跳板星球，那么此时直接跳跃肯定要更优秀一些。假设我们有至少一次跳成功了，那么这种情况的时间一定在 u 已经考虑过了（如果 v 跳成功，就钦定 u 这次一定跳成功；如果 v 失败了，就钦定 u 这次也失败了，这样一定能保证 u 和 v 到达根的时间一样）。唯一一种 u 无法复制的情况就是 v 每次跳跃都失败了，此时它就会多走一条 v 到 u 的边，概率是 p^{cnt}（cnt 是 v 到根路径上跳板星球的数量），因此对答案的贡献就会家上 p^{cnt}，因此 dp_v = dp_u + p^{cnt}，那么这道题就做完了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
struct Edge{
    int v, nex;
} e[N << 1], e2[N];
int head[N], ecnt;
void addEdge(int u, int v){
    e[++ecnt] = Edge{v, head[u]};
    head[u] = ecnt;
}
int flag[N], n, m;
double dp[N], p, ans;
void dfs(int u, int fa, double pp){
    if(flag[fa])
        pp *= p;
    if(u != 1){
        if(flag[fa])
            dp[u] = dp[fa] + 1;
        else
            dp[u] = dp[fa] + pp;
    }
    ans += dp[u];
    for(int i = head[u]; i; i = e[i].nex){
        int v = e[i].v;
        if(v == fa)
            continue;
        dfs(v, u, pp);
    }
    pp /= p;
}
int main(){
    scanf("%d%d%lf", &n, &m, &p);
    for(int i = 1; i < n; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for(int i = 1; i <= m; i++){
        int u;
        scanf("%d", &u);
        flag[u] = true;
    }
    dfs(1, 0, 1);
    printf("%.2lf", ans / n);
    return 0;
}

P5011 水の造题

其实这道题目的样例解释已经把如何统计答案讲解的差不多了。

我们考虑 DP，设 dp_{i, j} 表示这是第 i 个动作，且第 i 个动作是 j 的期望。根据样例解释，我们可以先将期望改写成总和，那么 dp_{i, j} 的含义就变成了这是第 i 个动作，且第 i 个动作是 j 的威力和。我们再设 ans_i 表示填完前 i 个数的威力和，显然 ans_i = \displaystyle\sum dp_{i, j}，而答案就是 \displaystyle\frac{1}{k^n} ans_n。

我们枚举前一个字符 c 是什么，如果 c 不等于 j - 1（当然 c = k 时是 1），那么直接加上当前的威力值即可，因此 dp_{i, j} 首先要加上一个 \displaystyle\sum_{c \neq j - 1} dp_{i - 1, c} + a_j。

下面来考虑威力值的加成，那么前一个填的数字必须是 j - 1，那么 dp_{i, j} 还要加上一个 dp_{i - 1, j - 1} + 2 a_j + a_{j - 1}，那么总的转移方程就是 dp_{i, j} = \displaystyle\sum_{c \neq j - 1} (dp_{i - 1, c} + a_j) + dp_{i - 1, j - 1} + 2a_j + a_{j - 1} = \sum_c dp_{i - 1, c} + k a_j + a_j + a_{j - 1} = ans_{i - 1} + k a_j + a_j + a_{j - 1}，那么 ans_i = k \times ans_{i - 1} + (2 + k) \times sum（sum 为 a_1, a_2, \dots, a_k 之和），根据等比数列求和公式，ans_n 最终等于 sum \times [n k^{n - 1} + (2n - 2) k^{n - 2}]，除以 k^n 后就得到了答案 \displaystyle\frac{nk + 2n - 2}{k^2} \times sum。边读边取模即可。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int K = 1e6 + 9, MOD = 19491001;
int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') 
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = ((x << 1) + (x << 3) + (ch ^ 48)) % MOD;
        ch = getchar();
    }
    return x * f;
}
int qpow(int a, int b){
    int res = 1;
    while(b > 0){
        if(b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
int n, k, sum, a[K];
signed main(){
    n = read();
    k = read();
    for(int i = 1; i <= k; i++){
        scanf("%lld", &a[i]);
        sum = (sum + a[i]) % MOD;
    }
    printf("%lld", sum * (n * (k + 2) % MOD - 2 + MOD) % MOD * qpow(k * k % MOD, MOD - 2) % MOD);
    return 0;
}