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.

注

过于简单的 A,B,C,D,E,H 不再赘述。

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

F. LCS

先求出 LCS，然后从后往前逆推一遍，具体地，从

(n,m)

开始推，记现在到了

(x,y)

，则：

若 $s[x] = t[y]$ $s [x] = t [y]$ ，说明这一位匹配，记录答案（先存起来，因为顺序是反着的），并推到 $x = y$ $x = y$ 。
- 解释：对应转移 $dp[x][y] = dp[x-1][y-1] + 1$ 。
否则，这一位不匹配，找到 $dp[x][y-1],dp[x-1][y]$ $d p [x] [y - 1], d p [x - 1] [y]$ 中较大的转移过去，具体地：
- 若 $dp[x][y-1] < dp[x-1][y]$ ， $x \to x-1$ ；
- 否则， $y \to y-1$ 。
- 解释：对应转移 $dp[x][y] = \max(dp[x-1][y],dp[x][y-1])$ 。

G. Longest Path

DAG 最长路，拓扑排序的过程中记录

f[u]

表示走到

u

的最长路，注意答案是

\max f[u]

I. Coins

概率 DP，设

dp[i][j]

表示前

i+j

枚硬币，扔出

i

正

j

反的概率。

初值：

dp[0][0] = 1

。

转移：

$dp[i][j] = dp[i-1][j] \times p + dp[i][j-1] \times (1-p)$ 。
边界转移：
- $dp[i][0] = dp[i-1][0] \times p$ 。
- $dp[0][i] = dp[0][i-1] \times (1-p)$ 。

时间复杂度

O(n^2)

。到这里足以 AC 本题了。

不过我们还可以优化一下，发现我们关注的是

i-j

的值，因此可以把状态缩减到一维。

设

dp[j]

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

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

假设我们现在已经抛了

i

枚硬币，那么此时

j

的奇偶性一定与

i

相同。

原因很简单，分讨一下：

若 $i$ 为奇数，那么正、反可能分别为：奇、偶；偶、奇。而奇 - 偶 = 偶 - 奇 = 奇。
若 $i$ 为偶数，那么正、反可能分别为：偶、偶；奇、奇。而奇 - 奇 = 偶 - 偶 = 偶。

那么更新时注意下奇偶性即可，优化表现在空间上，空间复杂度

O(n^2)

降到

O(n)

。

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

代码

CPP

#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

，完全没问题。

接下来看转移：

如果取了有 $3$ 个寿司的盘子；
- 概率为 $\frac{i}{n}$ 。
- 转移到 $dp[i-1][j+1][k]$ （因为有个 $3$ 的盘子变成了 $2$ ），并且期望 $+1$ 。
- 即： $dp[i][j][k] \gets (dp[i-1][j+1][k]+1) \times \frac{i}{n}$ .
如果取了有 $2$ 个寿司的盘子；
- 概率为 $\frac{j}{n}$ 。
- 转移到 $dp[i][j-1][k+1]$ （因为有个 $2$ 的盘子变成了 $1$ ），并且期望 $+1$ 。
- 即： $dp[i][j][k] \gets (dp[i][j-1][k+1]+1) \times \frac{j}{n}$ .
如果取了有 $1$ 个寿司的盘子；
- 概率为 $\frac{k}{n}$ 。
- 转移到 $dp[i][j][k-1]$ （因为有个 $1$ 的盘子变成了 $0$ ），并且期望 $+1$ 。
- 即： $dp[i][j][k] \gets (dp[i][j][k-1]+1) \times \frac{k}{n}$ .
如果取了有 $0$ 个寿司的盘子；
- 概率为 $\frac{n-i-j-k}{n}$ 。
- 转移到 $dp[i][j][k]$ （因为有个 $0$ 的盘子变成了 $0$ ，本质不变），并且期望 $+1$ 。
- 即： $dp[i][j][k] \gets (dp[i][j][k]+1) \times \frac{n-i-j-k}{n}$ .

整理得到转移式子：

\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}

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

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

除 $0$ 错误在 double 类型中 不会 RE，会变成 $\text{inf}$ 。
由于转移存在 $-1$ ，因此注意 $i = 0,j=0,k=0$ 三种情况。
取值范围， $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$ 。

代码

CPP

#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

后手）。

代码

CPP

#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】

INPUT1

2 3
1 2

【输出 #1】

OUTPUT1

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)

。

代码

CPP

#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（所取的数作为 $X$ $X$ ，要求 $X-Y$ $X - Y$ 尽可能大）：
- 如果取 $a[l]$ ，那么答案变为 $a[l]+dp[l+1][r]$ 。
- 如果取 $a[r]$ ，那么答案变为 $a[r] + dp[l][r-1]$ 。
- 由此，转移 $dp[l][r] = \max(a[l]+dp[l+1][r],a[r]+dp[l][r-1])$ 。
若此时轮到 B（所取的数作为 $Y$ $Y$ ，要求 $X-Y$ $X - Y$ 尽可能小）：
- 如果取 $a[l]$ ，那么答案变为 $dp[l+1][r]-a[l]$ 。
- 如果取 $a[r]$ ，那么答案变为 $dp[l][r-1]-a[r]$ 。
- 由此，转移 $dp[l][r] = \max(dp[l+1][r]-a[l],dp[l][r-1]-a[r])$ 。

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

若 A 取（作 $X$ ）： $dp[i][i] = a[i]$ 。
若 B 取（作 $Y$ ）： $dp[i][i] = -a[i]$ 。

答案即为

dp[1][n]

。

时空复杂度

O(n^2)

。

代码

CPP

#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)

。

Trick

由于本题中允许分

0

个糖果，因此

sum[0]

存在且不为

0

。

因此

sum[0-1]

时会出现越界问题，我们不妨把

sum[i]

的实际值存在

sum[i+1]

上，即下标统一加一。

这样就可以很好的避免这个问题，查询时从”上界不变，下界

-1

“ 变为 “上界

+1

，下界不变” 即可。

还可以进一步优化，发现

dp

数组的转移和第一维

i

无关，可以直接优化掉一维。

空间复杂度优化到

O(n)

。

代码

CPP

#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 了？？？

n \le 21

很小，考虑一些

2^n

之类的做法。

我们设

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)

，所以这个对应关系是唯一的，因此直接省去是正确的。

代码

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

树形 DP，类似 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)

。

代码

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

一句话题意：带权 LIS。

如果不会 LIS 的

O(n \log n)

做法，可以先学一下 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)

，树状数组也可以，因为这里是前缀最大值。

代码

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

设

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)

。

时间复杂度解析

矩阵大小：

O(n^2)

。

矩阵乘法：时间复杂度

O(n^3)

。

快速幂：时间复杂度

O(\log k)

。

实际上还有一个

2

倍以上的常数，因为快速幂要矩阵乘法两次。

代码

CPP

#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 统计答案的思路是，从高到低枚举数位，然后固定枚举过的位置，计算后面的方案数。

举例

举个例子，我们现在要计算

K = 20251114

的答案，那么过程如下：

枚举到最高位 $2$ $2$ ，这一位上如果放 $0 \sim 1$ $0 \sim 1$ ，那么后面的可以随便放，统计答案。
- 此时相当于拼成了 $SXXXXXXX$ ，其中 $S$ 表示这一位可以放的值，即 $0 \sim 1$ 。
枚举到次高位 $0$ ，这一位上不管放什么，后面的都不能随便放，不统计答案。
枚举到下一位 $2$ $2$ ，这一位上如果放 $0 \sim 1$ $0 \sim 1$ ，那么后面的可以随便放，统计答案。
- 此时相当于拼成了 $20SXXXXX$ ，其中 $S$ 表示这一位可以放的值，即 $0 \sim 1$ 。
枚举到下一位 $5$ $5$ ，这一位上如果放 $0 \sim 4$ $0 \sim 4$ ，那么后面的可以随便放，统计答案。
- 此时相当于拼成了 $202SXXXX$ ，其中 $S$ 表示这一位可以放的值，即 $0 \sim 4$ 。
枚举到下一位 $1$ $1$ ，这一位上如果放 $0$ $0$ ，那么后面的可以随便放，统计答案。
- 此时相当于拼成了 $2025SXXX$ ，其中 $S$ 表示这一位可以放的值，即 $0$ 。
枚举到下一位 $1$ $1$ ，这一位上如果放 $0$ $0$ ，那么后面的可以随便放，统计答案。
- 此时相当于拼成了 $20251SXX$ ，其中 $S$ 表示这一位可以放的值，即 $0$ 。
枚举到下一位 $1$ $1$ ，这一位上如果放 $0$ $0$ ，那么后面的可以随便放，统计答案。
- 此时相当于拼成了 $202511SX$ ，其中 $S$ 表示这一位可以放的值，即 $0$ 。
枚举到下一位 $4$ $4$ ，这一位上放 $0 \sim 4$ $0 \sim 4$ 都是可以的，统计答案。
- 此时相当于拼成了 $2025111S$ ，其中 $S$ 表示这一位可以放的值，即 $0\sim 4$ 。

我们发现，对于非最后一位（记作第

i

位）上的数

x_i

，该位上如果放

0 \sim (x_i - 1)

，后面的都可以随便放。而后面随便放的方案数我们又算出来了，因此枚举第

i

位上放什么，然后统计求和即可。

对于最后一位，特别地记得加上最后一位放

x

的方案数即可。

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

统计答案的代码

CPP

12345678910111213for (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

的位数。

代码

CPP

#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;
}

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

Atcoder Educational DP Contest 题解

文章操作

F. LCS

G. Longest Path

I. Coins

J. Sushi

K. Stones

L. Deque

M. Candies

N. Slimes

O. Matching

P. Independent Set

Q. Flowers

R. Walk

S. Digit Sum

相关推荐

评论

Atcoder Educational DP Contest 题解