Atcoder Educational DP Contest 题解

· · 题解

update on 2025.11.10 11:25 完成 F,G,I,J.

update on 2025.11.10 17:30 完成 K,L,M,N,O.

update on 2025.11.10 21:45 完成 P,Q,R.

update on 2025.11.14 22:07 完成 S.

:::info[注]{open} 过于简单的 A,B,C,D,E,H 不再赘述。

目前尚未完成 T,U,V,W,X,Y,Z 共 7 题题解。 :::

F. LCS

先求出 LCS，然后从后往前逆推一遍，具体地，从 (n,m) 开始推，记现在到了 (x,y)，则：

G. Longest Path

DAG 最长路，拓扑排序的过程中记录 f[u] 表示走到 u 的最长路，注意答案是 \max f[u].

I. Coins

概率 DP，设 dp[i][j] 表示前 i+j 枚硬币，扔出 i 正 j 反的概率。

初值：dp[0][0] = 1。

转移：

时间复杂度 O(n^2)。到这里足以 AC 本题了。

不过我们还可以优化一下，发现我们关注的是 i-j 的值，因此可以把状态缩减到一维。

设 dp[j] 表示到目前位置正的硬币数量比反着的 多了 j 个 的概率。

转移类似，不过注意一个问题。

假设我们现在已经抛了 i 枚硬币，那么此时 j 的奇偶性一定与 i 相同。

原因很简单，分讨一下：

那么更新时注意下奇偶性即可，优化表现在空间上，空间复杂度 O(n^2) 降到 O(n)。

这种只关注两维差值的 DP 的这种 Trick 很常见，比如 [CSP-S 2019] Emiya 家今天的饭 中也有应用。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
int n;
double ans,p,dp[6005];
int main()
{
    scanf("%d",&n);
    dp[n] = 1;
    for (int i=1;i<=n;i++)
    {
        scanf("%lf",&p);
        for (int j=n-i;j<=n+i;j++)
        {
            if (i % 2 == (j+n) % 2) dp[j] = dp[j-1] * p + dp[j+1] * (1-p);
        }
    }
    for (int i=1;i<=n;i+=2) ans += dp[n+i];
    printf("%.10lf",ans);
    return 0;
}

:::

J. Sushi

蛮好的一道 期望 DP 入门题。

很容易发现 a_i 特别小，并且各个 a_i 之间与位置没有关系。

换而言之，1 3 2 和 2 3 1 的答案是相同的，因为每次选中各个盘子的概率相同。

因此，我们考虑设 dp[i][j][k] 表示盘子里有 3,2,1 个寿司的盘子分别有 i,j,k 个时，全部吃完的期望。

这个状态定义空间是 O(n^3) 的，而 n \le 300，完全没问题。

接下来看转移：

整理得到转移式子：

\begin{align} dp[i][j][k] = \ \ &(dp[i-1][j+1][k]+1) \times \frac{i}{n} \\ + \ &(dp[i][j-1][k+1]+1) \times \frac{j}{n} \\ + \ &(dp[i][j][k-1]+1) \times \frac{k}{n} \\ + \ &(dp[i][j][k]+1) \times \frac{n-i-j-k}{n} \end{align}

发现存在「自己转移到自己」的情况，不满足 DP「无后效性」的要求。

怎么办？移项！

先把 dp[i][j][k] 拆开：

\begin{align} dp[i][j][k] = \ \ &(dp[i-1][j+1][k]+1) \times \frac{i}{n} \\ + \ &(dp[i][j-1][k+1]+1) \times \frac{j}{n} \\ + \ &(dp[i][j][k-1]+1) \times \frac{k}{n} \\ + \ &dp[i][j][k] \times \frac{n-i-j-k}{n} + \frac{n-i-j-k}{n} \end{align}

再移项：

\begin{align} dp[i][j][k] - dp[i][j][k] \times \frac{n-i-j-k}{n} = \ \ &(dp[i-1][j+1][k]+1) \times \frac{i}{n} \\ + \ &(dp[i][j-1][k+1]+1) \times \frac{j}{n} \\ + \ &(dp[i][j][k-1]+1) \times \frac{k}{n} \\ + \ &\frac{n-i-j-k}{n} \end{align}

合并同类项，两边同时乘上 n：

\begin{align} dp[i][j][k] \times (i+j+k) = \ \ &(dp[i-1][j+1][k]+1) \times {i} \\ + \ &(dp[i][j-1][k+1]+1) \times {j} \\ + \ &(dp[i][j][k-1]+1) \times {k} \\ + \ &{n-i-j-k} \end{align}

把左边的系数 (i+j+k) 移过去，得到最终转移式：

\begin{align} dp[i][j][k] = \ \ &(dp[i-1][j+1][k]+1) \times \frac{i}{i+j+k} \\ + \ &(dp[i][j-1][k+1]+1) \times \frac{j}{i+j+k} \\ + \ &(dp[i][j][k-1]+1) \times \frac{k}{i+j+k} \\ + \ &\frac{n-i-j-k}{i+j+k} \end{align}

根据上面的转移式转移即可，注意几点：

  1. 初始化 dp[0][0][0] = 0，不要把 i+j+k = 0（即 i,j,k=0 时再转移一下，否则除 0 错误）。

    除 0 错误在 double 类型中 不会 RE，会变成 \text{inf}。

  2. 由于转移存在 -1，因此注意 i = 0,j=0,k=0 三种情况。

  3. 取值范围，0 \le i \le \sum_p [a[p]=3],0 \le j \le \sum_p [a[p]\ge 2],0 \le k \le \sum_p [a[p]\ge 1]。

    注意后面两者，因为 3 会变成 2，2 会变成 1。

:::success[代码] 

#include <bits/stdc++.h>
using namespace std;
int n,x,c[4];
double dp[305][305][305];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        c[x]++;
    }
    for (int i=0;i<=c[3];i++)
    {
        for (int j=0;j<=c[2]+c[3];j++)
        {
            for (int k=0;k<=c[1]+c[2]+c[3];k++)
            {
                if (i+j+k == 0) continue;
                if (i) dp[i][j][k] += (dp[i-1][j+1][k]+1) * (i*1.0/(i+j+k));
                if (j) dp[i][j][k] += (dp[i][j-1][k+1]+1) * (j*1.0/(i+j+k));
                if (k) dp[i][j][k] += (dp[i][j][k-1]+1) * (k*1.0/(i+j+k));
                dp[i][j][k] += (n-(i+j+k))*1.0/(i+j+k);
            }
        }
    } 
    printf("%.10lf",dp[c[3]][c[2]][c[1]]);
    return 0;
}

:::

K. Stones

坑，开始一眼完全背包，设 dp[i] 表示还有 i 个石子时谁必胜（1 先手，0 后手）。

:::warning[代码]{open}

#include <bits/stdc++.h>
using namespace std;
int n,k,x;
bool dp[100005];
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for (int j=x;j<=k;j++)
        {
            dp[j] = dp[j] | (dp[j-x]^1);
        }
    }
    if (dp[k]) puts("First");
    else puts("Second");
    return 0;
}

:::

过了所有样例，But Wrong Answer.

为什么？发现 Hack：

【输入 #1】

2 3
1 2

【输出 #1】

Second

因此，错误的原因就在 dp[j] = dp[j] | (dp[j-x]^1); 这行。因为 dp[j-x] 可能此时 并不是全局最优决策，我们就把它用上了，所以会导致后面决策的问题。

在这个 Hack 中的表现就是，初始 dp[2] = 0，然后更新 dp[3] = dp[2] \oplus 1 = 0 \oplus 1 = 1。

异或的原因是先后手互换。

所以内外层循环换个位置即可，时间复杂度 O(nk)。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
int n,k,a[105];
bool dp[100005];
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=k;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (i-a[j] < 0 || dp[i-a[j]]) continue;
            dp[i] = 1;
            break; 
        }
    }
    if (dp[k]) puts("First");
    else puts("Second");
    return 0;
}

:::

L. Deque

可以先看这道题 iai 2024年3月乙组 - 交替取数，没有太多的分类讨论，但思路相似。

发现每次取完之后剩下的都是一个区间，考虑 区间 DP。

设 dp[l][r] 为区间 [l,r] 的答案（X-Y），那么我们可以根据 len = r-l+1 计算出来此时该大郎（下文记作 A）还是二郎（下文记作 B）操作。

具体地，若 len\bmod 2 = n \bmod 2，此时该 A，反之轮到 B，比较好想。

那么根据操作方分类讨论：

最后看初值，对 A、B 取最后一个分类讨论。

答案即为 dp[1][n]。

时空复杂度 O(n^2)。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
#define intt long long
int n;
intt a[3005],dp[3005][3005];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if (n % 2) dp[i][i] = a[i];
        else dp[i][i] = -a[i];
    }
    for (int len=2;len<=n;len++)
    {
        for (int l=1;l+len-1<=n;l++)
        {
            int r = l+len-1;
            if (len % 2 == n % 2)
            {
                dp[l][r] = max(a[l]+dp[l+1][r],a[r]+dp[l][r-1]);
            }
            else
            {
                dp[l][r] = min(dp[l+1][r]-a[l],dp[l][r-1]-a[r]);
            }
        }
    }
    printf("%lld",dp[1][n]);
    return 0;
}

:::

M. Candies

显然的 DP：设 dp[i][j] 表示前 i 个人一共发了 j 个糖果。

边界：dp[0][0] = 1，目标：dp[n][k]。

转移只需枚举给第 i 个人发了 s 个糖果：

dp[i][j] = \sum_{s=0}^{\min(j,a[i])} dp[i-1][j-k]

时间复杂度 O(nk^2)，无法通过。

发现这个形式是一段 DP 数组的求和，可以写成前缀和的形式。

具体地，记 sum[i] = \sum_{j=0}^i dp[i-1][j]，那么转移可写作：

dp[i][j] = sum[j] - sum[j-\min(j,a[i])-1]

又因为 sum 数组只需要对 dp[i][*] 更新完后扫一次即可，因此 sum 的计算是 O(nk) 的。

这种优化方式被称为 前缀和优化 DP。

总时空复杂度均为 O(nk)。

:::info[Trick]{open}

由于本题中允许分 0 个糖果，因此 sum[0] 存在且不为 0。

因此 sum[0-1] 时会出现越界问题，我们不妨把 sum[i] 的实际值存在 sum[i+1] 上，即下标统一加一。

这样就可以很好的避免这个问题，查询时从”上界不变，下界 -1“ 变为 “上界 +1，下界不变” 即可。 :::

还可以进一步优化，发现 dp 数组的转移和第一维 i 无关，可以直接优化掉一维。

空间复杂度优化到 O(n)。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int p = 1e9+7;
int n,k,x;
int sum[100005],dp[100005];
int mod(int x)
{
    if (x < 0) x += p;
    if (x >= p) x -= p;
    return x;
}
int main()
{
    scanf("%d%d",&n,&k);
    dp[0] = 1;
    for (int j=0;j<=k;j++) sum[j+1] = 1;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for (int j=0;j<=k;j++)
        {
            dp[j] = mod(sum[j+1]-sum[j-min(j,x)]);
        }
        for (int j=0;j<=k;j++) 
        {
            sum[j+1] = mod(sum[j]+dp[j]);
        }
    }
    printf("%d",dp[k]);
    return 0;
}

:::

N. Slimes

同 P1775. 石子合并（弱化版），区间 DP 枚举分界点即可。

O. Matching

我居然切蓝的 DP 了？？？

我们设 $dp[i][x]$ 表示前 $i$ 个男人，选择女人的集合为 $x$（$0$ 表示未选，$1$ 表示已选）时的方案数。 那么初值有 $dp[0][0] = 1$，其他为 $0$。 目标必须是男女两两匹配，即 $dp[n][2^n-1]$。 转移就是枚举集合 $x$，对于 $a[i][j] = 1$ 的 $j$，如果其在集合中，那么除去 $j$ 的结果加在一起即可。 记 $x$ 二进制表示中 $1$ 的个数为 $count(x)$，$x$ 二进制第 $j$ 位为 $x_j$，则形式化的，有： $$ dp[i][x] = \sum_{count(x) = i} \sum_{x_j = 1} dp[i-1][x - 2^j] $$ 直接这样做，时间复杂度是 $O(n^22^n)$ 的，虽说跑不满，但是特别悬。 考虑优化：注意到对于不同的 $i$，$count(x)$ 的要求是不同的，因此考虑预处理出来 $count(x) = i$ 的各个集合 $s[i]$。 这样虽然还是三层循环，但是均摊复杂度是 $O(n 2^n)$ 的了，可以通过本题。 --- 另外，发现 $dp$ 数组的第一维没有作用，可以直接省去。 正确性方面，第一维的 $i$ 其实就是 $count(x)$，所以这个对应关系是唯一的，因此直接省去是正确的。 :::success[代码] ```cpp #include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7; int n,a[25][25],sum; vector<int> s[25]; int dp[(1<<21)+5]; int mod(int &x,int y) { x = x + y; if (x >= MOD) x -= MOD; return x; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { for (int j=0;j<n;j++) { scanf("%d",&a[i][j]); } } for (int j=0;j<(1<<n);j++) { sum = 0; for (int k=0;k<n;k++) { if (j & (1<<k)) sum++; } s[sum].push_back(j); } dp[0] = 1; for (int i=1;i<=n;i++) { for (int j=0;j<(int)s[i].size();j++) { for (int k=0;k<n;k++) { if (a[i][k] == 0) continue; if ((s[i][j] & (1<<k)) == 0) continue; dp[s[i][j]] = mod(dp[s[i][j]],dp[s[i][j]-(1<<k)]); } } } printf("%d",dp[(1<<n)-1]); return 0; } ``` ::: ## [P. Independent Set](https://hydro.ac/d/topoac/p/AtDP1016) 树形 DP，类似 [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352)。 设 $f[u][0/1]$ 表示把节点 $u$ 染成黑色 / 白色时，**以 $u$ 为根的子树内染色的方案数**。 由于各子节点的染色方案间 **互相独立**，因此是 **乘法原理**，有： $$ \begin{align} f[u][0] &= \prod_v (f[v][0] + f[v][1]) \\ f[u][1] &= \prod_v f[v][0] \end{align} $$ 时间复杂度 $O(n)$。 :::success[代码] ```cpp #include <bits/stdc++.h> using namespace std; #define intt long long const int N = 100005, M = 200005; const int mod = 1e9+7; int n,u,v,cnt; intt f[N][2]; int head[N],ver[M],nxt[M]; void add(int x,int y) { ver[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; } void dfs(int u,int fa) { f[u][0] = 1; f[u][1] = 1; for (int i=head[u];i;i=nxt[i]) { int v = ver[i]; if (v == fa) continue; dfs(v,u); f[u][0] = (f[u][0]*(f[v][0]+f[v][1])%mod)%mod; f[u][1] = (f[u][1]*f[v][0])%mod; } } int main() { scanf("%d",&n); for (int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,0); printf("%lld",(f[1][0]+f[1][1])%mod); return 0; } ``` ::: ## [Q. Flowers](https://hydro.ac/d/topoac/p/AtDP1017) 一句话题意：带权 LIS。 如果不会 LIS 的 $O(n \log n)$ 做法，可以先学一下 [P1439 两个排列的最长公共子序列](https://www.luogu.com.cn/problem/P1439)，虽然说是“LCS”，但实际转化后就是 LIS。 考虑朴素：设 $dp[i]$ 表示以 $i$ 结尾（结尾高度为 $h[i]$）时的答案。 那么有转移： $$ dp[i] = \max_{1\le j < i,h[j] < h[i]} dp[j] + a[i] $$ 显然我们需要找到 $1\le j < i$ 范围内，满足 $h[j] < h[i]$ 条件下最大的 $dp[j]$，直接线段树单点修改区间查询最大值。 时间复杂度 $O(n \log n)$，树状数组也可以，因为这里是前缀最大值。 :::success[代码] ```cpp #include <bits/stdc++.h> using namespace std; #define intt long long const int N = 200005, M = 800005; int n,h[N]; intt a[N],t[M],dp[N],ans; #define mid ((l+r)>>1) #define ls (p<<1) #define rs ((p<<1)|1) void update(int p) { t[p] = max(t[ls],t[rs]); return; } void change(int p,int l,int r,int x,intt d) { if (l == r) { t[p] = max(t[p],d); return; } if (x <= mid) change(ls,l,mid,x,d); else change(rs,mid+1,r,x,d); update(p); } intt query(int p,int l,int r,int q) { if (r <= q) return t[p]; intt res = query(ls,l,mid,q); if (q > mid) res = max(res,query(rs,mid+1,r,q)); return res; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&h[i]); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) { dp[i] = query(1,1,n+1,h[i]) + a[i]; change(1,1,n+1,h[i]+1,dp[i]); ans = max(ans,dp[i]); } printf("%lld",ans); return 0; } ``` ::: ## [R. Walk](https://hydro.ac/d/topoac/p/AtDP1018) 设 $dp[u][i]$ 表示以 $u$ 为终点的长度为 $i$ 的路径条数，初始有 $dp[u][0] = 1$。 考虑转移，假设 $v$ 对应 $v \to u$ 的边的起点，那么转移有 $$ dp[u][i] = \sum_v dp[v][i-1] $$ 考虑 $v \to u$ 的边在邻接矩阵上的性质：若 $a_{v,u} = 1$，表明存在此边。 因此，转移也可以写作： $$ dp[u][i] = \sum_{v=1}^n dp[v][i-1] \times a[v][u] $$ 注意到 $u$ 固定时，$a[v][u]$ 是矩阵上的某一列。 也就是说，转移就是对矩阵 $a$ 的第 $u$ 列的每一项分别乘上了 $dp$ 对应的值，并且求和。 这不就是 **矩阵乘法** 的形式吗？也就是说，我们可以写作： $$ \begin{bmatrix} dp[1][i] & dp[2][i] & \cdots & dp[n][i] \end{bmatrix} = \begin{bmatrix} dp[1][i-1] & dp[2][i-1] & \cdots & dp[n][i-1] \end{bmatrix} \times \begin{bmatrix} a[1][1] & a[1][2] & \cdots & a[1][n]\\ a[2][1] & a[2][2] & \cdots & a[2][n]\\ \vdots & \vdots & \ddots & \vdots \\ a[n][1] & a[n][2] & \cdots & a[n][n] \\ \end{bmatrix} $$ 注意到 $dp$ 第二维可以省去，变为： $$ \begin{bmatrix} dp[1] & dp[2] & \cdots & dp[n] \end{bmatrix} = \begin{bmatrix} dp[1] & dp[2] & \cdots & dp[n] \end{bmatrix} \times \begin{bmatrix} a[1][1] & a[1][2] & \cdots & a[1][n]\\ a[2][1] & a[2][2] & \cdots & a[2][n]\\ \vdots & \vdots & \ddots & \vdots \\ a[n][1] & a[n][2] & \cdots & a[n][n] \\ \end{bmatrix} $$ 如果转移 $k$ 次，式子就变为了（注意矩阵右上角的幂次）： $$ \begin{bmatrix} dp[1] & dp[2] & \cdots & dp[n] \end{bmatrix} = \begin{bmatrix} dp[1] & dp[2] & \cdots & dp[n] \end{bmatrix} \times {\begin{bmatrix} a[1][1] & a[1][2] & \cdots & a[1][n]\\ a[2][1] & a[2][2] & \cdots & a[2][n]\\ \vdots & \vdots & \ddots & \vdots \\ a[n][1] & a[n][2] & \cdots & a[n][n] \\ \end{bmatrix}}^{\large k} $$ 又因为初始 $dp[i] = 1$，则式子可写作： $$ \begin{bmatrix} dp[1] & dp[2] & \cdots & dp[n] \end{bmatrix} = \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix} \times {\begin{bmatrix} a[1][1] & a[1][2] & \cdots & a[1][n]\\ a[2][1] & a[2][2] & \cdots & a[2][n]\\ \vdots & \vdots & \ddots & \vdots \\ a[n][1] & a[n][2] & \cdots & a[n][n] \\ \end{bmatrix}}^{\large k} $$ 直接矩阵快速幂加速即可，最终结果即 $\sum_i dp[i]

时间复杂度 O(n^3 \log k)。

:::info[时间复杂度解析]{open}

矩阵大小：O(n^2)。

矩阵乘法：时间复杂度 O(n^3)。

快速幂：时间复杂度 O(\log k)。

实际上还有一个 2 倍以上的常数，因为快速幂要矩阵乘法两次。 :::

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
#define intt long long 
const int mod = 1e9+7;
int n;
intt sum,k;
struct martix
{
    intt a[55][55];
}a,ans;
martix multi(martix x,martix y)
{
    martix res;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            res.a[i][j] = 0;
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            for (int k=1;k<=n;k++)
            {
                res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;    
            }   
        } 
    }
    return res;
}
martix qpow(martix x,intt y)
{
    martix res;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            res.a[i][j] = 0;
        }
        res.a[i][i] = 1;
    }
    while (y)
    {
        if (y & 1) res = multi(res,x);
        x = multi(x,x);
        y >>= 1;
    }
    return res;
}
int main()
{
    scanf("%d%lld",&n,&k);
    for (int i=1;i<=n;i++)
    {
        ans.a[1][i] = 1;
        for (int j=1;j<=n;j++)
        {
            scanf("%lld",&a.a[i][j]);
        }
    }
    ans = multi(ans,qpow(a,k));
    for (int i=1;i<=n;i++)
    {
        sum = (sum + ans.a[1][i]) % mod;
    }
    printf("%lld",sum);
    return 0;
}

:::

S. Digit Sum

数位 DP 模板题。

看到「十进制数位之和是 D 的倍数」这样倍数的字眼，一个很经典的做法是转化为「十进制数位之和 \bmod D = 0」。

这样倍数转「取模为 0」的技巧还是很常用的，例如 [NOIP 2016 提高组] 组合数问题，转化后就是个递推组合数。

那么我们考虑设 dp[i][j] 表示 i 位数字，数位之和 \bmod D = j 的数字个数。

考虑转移，显然需要枚举 i,j，以及这一位填入的数字 k \in [0,9]。

那么转移有：

dp[i][(j+k)\bmod D] \gets dp[i-1][j]

稍微解释一下，这个转移是求和的形式，就是考虑填上这个数 k 后数位之和 \bmod D 从原来的 j 变为了 (j+k) \bmod D。

初值是 dp[0][0] = 1，其余为 0，这个还是很好理解的。

接下来我们考虑数位 DP 中我认为细节较多且较为困难的部分： 统计答案。

一般数位 DP 统计答案的思路是，从高到低枚举数位，然后固定枚举过的位置，计算后面的方案数。

:::info[举例] 举个例子，我们现在要计算 K = 20251114 的答案，那么过程如下：

:::

我们发现，对于非最后一位（记作第 i 位）上的数 x_i，该位上如果放 0 \sim (x_i - 1)，后面的都可以随便放。而后面随便放的方案数我们又算出来了，因此枚举第 i 位上放什么，然后统计求和即可。

对于最后一位，特别地记得加上最后一位放 x 的方案数即可。

这个统计可能比较抽象，可以结合代码看看：

:::info[统计答案的代码]{open}

for (int i=n;i>=1;i--)
{
    for (int j=0;j<(int)(s[n-i+1]-'0')+(i==1);j++)
    {
        //这里的 s 是用 char 数组的形式存的 K，最高位对应的是 s[1]，最低 s[n]。
        ans = mod(ans + dp[i-1][((d-(x+j)%d)%d]);
        //这里解释一下，x 是这一位（第 i 位）之前的 K 的数位之和，
        //再算上这一位填的值 j，已经放的数位 mod d 的值是 (x+j)%d，
        //但是要凑成总的数位之和 mod d = 0，因此剩下还需要补一个 (d-(x+j)%d)%d。
    }
    x = (x+(int)(s[n-i+1]-'0')) % d;
    //这里就是统计下前面的数位之和，因为已经是固定的了。
}

:::

最后注意一下，这题求的计数是 1 \sim K，而我们最低位为 0 的也算进去了（不然后面没法转移，因为每次转移相当于在原来的数字前面再拼一位），而 0 对任何数 D 取模一定为 0，因此会对答案产生 1 的贡献，把最终答案 -1 即可。

总时间复杂度 O(|K|D \times 10)，其中 |K| 是 K 的位数。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
char s[10005];
int x,d,n,dp[10005][105],ans;
int mod(int x)
{
    if (x >= MOD) x -= MOD;
    return x; 
}
int dod(int x)
{
    while (x < 0) x += d;
    while (x >= d) x -= d;
    return x; 
}
int main()
{
    scanf("%s",s+1);
    n = strlen(s+1);
    scanf("%d",&d);
    dp[0][0] = 1;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<d;j++)
        {
            for (int k=0;k<=9;k++)
            {
                dp[i][dod(j+k)] = mod(dp[i][dod(j+k)]+dp[i-1][j]); 
            }
        }
    }
    for (int i=n;i>=1;i--)
    {
        for (int j=0;j<(int)(s[n-i+1]-'0')+(i==1);j++)
        {
            ans = mod(ans + dp[i-1][dod(-x-j)]);
        }
        x = dod(x+(int)(s[n-i+1]-'0'));
    }
    printf("%d",mod(MOD+ans-1));
    return 0;
}

:::

想明白了还是不难理解的。