P15966 合成西瓜 题解

Snowflake_Fairy

·

2026-03-28 21:50:32

·

题解

前言

蒟蒻一枚，做了两小时，才第 91 名，后面两道题甚至还没来得及看。

纪念 2026 年 3 月 28 日 Atcoder 第一次单场 perf 大于 2000。

解题思路

有点意思。看完题目后居然茫然了一阵。

定义 f(n) 为目标西瓜等级为 n 时的答案。

当 x \leq y 时，可以直接生成一个等级为 x 的西瓜，所以对于 0 \leq i \leq y, f(i) = 1。

当 x > y 时，我们先找到初始序列，再根据之后的情况往里面添加。根据贪心策略，肯定希望每一次都可以产生更高等级的西瓜。

所以初始时构造序列为 [0,1,2,\cdots, y]，再选择区间 [0, y + 1]，这样就有了等级为 y + 1 的西瓜，所以 f(y + 1) = y + 1，当然等价于因为需要等级小于 y + 1 的西瓜各一个，所以将所有等级小于 y + 1 的西瓜产生的代价都加起来，即 f(y + 1) = f(0) + f(1) + \cdots + f(y)。于是我们就可以推广为 i > y, f(i) = \displaystyle\sum_{k = 0} ^ {i - 1} f(k)。

然后发现这样递推是 \mathcal{O}(n^2) 的，所以可以使用一个变量 s，每一次 s 都增加 f(k)，再用一个答案变量每次累加 s，这样就优化成了 \mathcal{O}(n) 的了，于是你有了 70pts。

似乎没辙了，于是去刷了两个 U 放松一下，回来瞬间精神倍增，反正没事，就开始迭代。 \because f(y + 1) = y + 1$$ 且 $$f(y + 2) = \displaystyle\sum_{k = 0} ^ {y + 1} f(k)

\therefore f(y + 2) = f(y + 1) + y + 1 = 2f(y + 1) = 2(y + 1)

\therefore f(y + 3) = f(y + 2) + f(y + 1) + y + 1 = 2f(y + 2) = 4f(y + 1) = 4(y + 1)

\cdots

因此得到 f(y + p) = 2^{p - 1}(y + 1)，写一个快速幂就好了。

所以在遇到没有思路的时候可以适当放松一下，回来说不定就有了新的灵感。

备注：感谢 @SubtleFlicker 找到题解中的逻辑错误，现已更正。

CODE：

#include

using namespace std;

#define int long long

const int mod = 998244353;

inline int qmi(int a, int b) {

int res = 1;

while (b) {

if (b & 1) {

res = res * a % mod;

}

a = a * a % mod;

b >>= 1;

}

return res;

}

signed main() {

ios::sync_with_stdio(false);

ios_base::sync_with_stdio(false);

cin.tie(0), cout.tie(0);

//f(n) = y + 1, f(n + 1) = f(n) + n = 2n, f(n + 2) = f(n + 1) + f(n) + n = 2n + n + n = 4n, f(n + 3) = f(n + 2) + f(n + 1) + f(n) + n = 4n +2n + 2n = 8n

int T;

cin >> T;

while (T--) {

int x, y;

cin >> x >> y;

if (x <= y) {

cout << "1\n";

} else {

cout << qmi(2, x - y - 1) * (y + 1) % mod << "\n";

}

}

return 0;

}