洛谷P17224 搬家の题解 求赞求关注

userId_undefined
Binary_Dreamer
倔强青铜

2026-08-24 18:00:03

发布于：吉林

28阅读
0回复
0点赞

蒟蒻第一次写绿题题解（能写出来就是个奇迹了，版面设计上不要有太大要求，如有错误请大佬们指出，只要还没AFO呢就一定会尽快改正），走过路过还望大佬们点个关注留个赞（第一次用acgo，简直弱爆了awa）

P17224 [Math×Girl²] 搬家

题目传送门

题目描述

小魔女 A 和小魔女 S 有一个容量为 MM 的箱子和 NN 个物品。
物品按 11 到 NN 编号，第 ii 个物品的价值为 3N−i3^{N-i}。

小魔女 A 可以决定每个物品的大小：令其为 11 或 22。

小魔女 S 使用一个打包机，该打包机的装填策略如下：

  1. 优先装大小为 11 的物品：在大小为 11 的物品中，按编号从小到大依次尝试装入，直到箱子装满或所有大小为 11 的物品都被装入。
  2. 再装大小为 22 的物品：若还有剩余容量，在大小为 22 的物品中，按编号从小到大依次尝试装入，直到箱子装满或所有大小为 22 的物品都被装入。

小魔女 S 希望装入物品的总价值最大。如果打包机的结果不是最优解，她会手动调整为最优解。
她不知道小魔女 A 要怎么设定物品大小，所以她想知道有多少种给物品分配大小的方案，使她无需手动调整？
答案对 998244353998244353 取模。

输入格式

一行两个正整数 N,MN,M。

输出格式

一行一个整数，表示方案数对 998244353998244353 取模后的结果。

输入输出样例 #1

输入 #1

 2 2

输出 #1

3

输入输出样例 #2

输入 #2

 114 514

输出 #2

304170860

输入输出样例 #3

输入 #3

 1919 810

输出 #3

310652647

说明/提示

样例解释

对样例 #1：有 22=42^2=4 种分配方案。

物品大小 打包机装入的物品 最优方案
1,11,1 {1,2}\{1,2\} {1,2}\{1,2\}
1,21,2 {1}\{1\} {1}\{1\}
2,12,1 {2}\{2\} {1}\{1\}
2,22,2 {1}\{1\} {1}\{1\}

共有 33 种方案符合要求。

数据范围与约定

本题开启捆绑测试。

子任务 分值 N,M≤N,M\le 特殊性质
11 1010 10710^7 M≥2NM\ge2N
22 2020 1010 -
33 3030 50005000
44 4040 10710^7

对于 100%100\% 的数据，1≤N,M≤1071 \le N, M \le 10^7。

数学原理

根据第 i 个物品的价值为 3𝑁−𝑖3^𝑁−𝑖，可知任意一个物品价值大于其后面所有物品价值之和。
N=4时

i 1 2 3 4
3N−13^{N-1} 34−13^{4-1} 34−23^{4-2} 34−33^{4-3} 34−43^{4-4}
对应数值 27 9 3 1

贪心策略：尽量拿编号小的物品，直到装满容量 𝑀。

分情况讨论

情况 1：𝑀 ≥ 𝟐𝑵

这说明箱子总容量足够放下全部物品（所有物品就算全是 2，也能全部放下）
无论打包机怎么分配大小，也全能装进去，即等于最优解。

总方案数：2N mod 9982443532 ^ N\bmod998244353

情况 2：𝑀 < 𝟐𝑵

此时箱子不能放下所有的物品。
设 𝑘 为大小为 1 的物品总个数

情况 2.1：𝑘 ≥ 𝑀

大小为 1 的物品数量超过箱子容量，打包机出来后直接装入前 𝑀 个大小为 1 的物品。
后面的 𝑁 − 𝑀 个物品任意打包成大小 1 或大小 2。
则 打包结果 = 最优解

当大小为 1 的物品足够多时（𝑘 ≥ 𝑀），打包机只选大小为 1 的物品，不选择任何大小为 2 的品。

必须保证在装满之前，绝不会遇到任何一个大小为 2 的物品。

前 𝑀 − 1 个物品大小必须全为 1。
前 𝑀 − 1 个位置固定后，还剩下 𝑁 − 𝑀 + 1 个位置。这里必须至少有一个大小为 1，不能全为 2。

总方案数：𝟐𝑵−𝑴+𝟏−𝟏𝟐 ^ 𝑵−𝑴+𝟏 − 𝟏

情况 2.2：𝑘 < 𝑀

此时大小为 1 的物品只有 𝑘 个，打包机会先把这 𝑘 个 1 全部装入，剩余容量为：

𝑅=𝑀−𝑘𝑅 = 𝑀 − 𝑘

还能装大小为 2 的物品，最多能装：

𝑡=⌊𝑅2⌋𝑡 = \lfloor \frac{𝑅}{2} \rfloor

打包机选择的是：所有编号最小的 𝑡 个大小为 2 的物品。剩下未被选中的大小为 2 的物品 有 𝑁 − 𝑘 − 𝑡
个。
核心判定条件：
在遇到第一个未被选中的 2 时，箱子必须已经装满（或只剩下 1 个容量，装不下它）。

情况 2.2.1：𝑅 为奇数

打包机装完 k 个 1 和 t 个 2 后，剩余容量为 1，再也装不下任何 2。
此时，只要在遇到 2𝑡+1 之前，前 𝑘 + 𝑡 个物品恰好包含 𝑘 个 1 和 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡，那么最
优解扫描到这 𝑘 + 𝑡 个物品时，箱子正好装满（因为总大小为 𝑘 + 2𝑡 = 𝑀 − 1，，离满还差
1），遇到后面的 2 时只剩 1 容量，装不下。
这 𝑘 + 𝑡 个物品的排列中，只需要决定哪些位置放 1（其余放那 t 个特定的 2），
方案数为：

(k+tk)\binom{k + t}{k}

情况 2.2.2：𝑅 为偶数

打包机装完 k 个 1 和 t 个 2 后，箱子刚好装满（容量为 0）。
有效情况分两种（避免重复计数）：

1. 基础情况：

前 𝑘 + 𝑡 个物品包含全部 k 个 1 和 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡。
最优解扫完这 𝑘 + 𝑡 个物品后容量为 0。

基础方案数为：

(k+tk)\binom{k + t}{k}

2. 额外情况

如果前 𝑘 + 𝑡 − 1 个物品只包含 𝑘 − 1 个 1 和 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡 ，还剩下 1 个 1 没有出现。
此时，最优解扫完这 𝑘 + 𝑡 − 1 个物品后，剩余容量为 1，（因为总大小为 (𝑘 − 1) + 2𝑡 = 𝑀 − 1）。
它遇到后面的 2𝑡+1 时，因为容量只有 1，装不下它，只能继续往后扫描，直到遇到那最后
一个 1，把它装进去，箱子才正好装满。
为了保证不重复基础情况，最后一个 1 必须出现在第 𝑘 + 𝑡 个位置之后：
前 𝑘 + 𝑡 − 1 个位置中，选 𝑘 − 1 个放放 1，其余放 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡 ：有 (k+t−1k−1)\binom{k + t - 1}{k - 1} 种；
剩下的那一个 1，可以放在位置 𝑘 + 𝑡 + 1 到 𝑁 之之间的 任意位置 ，只要它后面全是未被选中的 2。

𝑁−(𝑘+𝑡+1)+1=𝑁−𝑘−𝑡𝑁 − (𝑘 + 𝑡 + 1) + 1 = 𝑁 − 𝑘 − 𝑡

额外方案数为：

(k+t−1k−1)×(N−k−t)\binom{k + t - 1}{k - 1} \times (N - k - t)

两部分加起来（基础与额外）：

(k+tk)+(k+t−1k−1)×(N−k−t)\binom{k + t}{k} + \binom{k + t - 1}{k - 1} \times (N - k - t)

参考代码：

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int MOD = 998244353; 
LL qpow(LL a, LL b)
{
	LL r = 1;
	while(b)
	{
		if(b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return r;
}
LL C(LL n, LL m, const vector<int> &fact, const vector<int> &invFact)
{
	if(m < 0 || n < 0 || m > n) return 0;
	return 1LL * fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}
int main()
{
	LL n, m; cin >> n >> m;
	LL ans = 0;
	if(m >= 2 * n)
	{
		ans = qpow(2, n);
	}
	else // 2 * n - m < 0
	{
		int N = max(n, (n + m) / 2 + 3);
		vector<int> fact(N + 1), invFact(N + 1);
		fact[0] = 1;
		for(int i = 1; i <= N; i++)
			fact[i] = 1LL * fact[i - 1] * i % MOD;
		invFact[N] = (int)qpow(fact[N], MOD -2);
		for(int i = N; i >= 1; i--)
			invFact[i - 1] = (int)(1LL * invFact[i] * i % MOD);
		int kMax = min(n, m - 1);
		int L = 2 * n - m;
		if(m <= n)
			ans = (qpow(2, n - m + 1) - 1 + MOD) % MOD;
		for(int k = 0; k <= kMax; k++)
		{
			if(k >= L)
				ans = (ans + C(n, k, fact, invFact)) % MOD;
			else
			{
				int d = m - k;
				int t = d / 2;
				int val = 0;
				if(d & 1) val = C(k + t, k, fact, invFact);
				else
				{
					val = C(k + t, k, fact, invFact);
					if(k > 0)
					{
						int add = 1LL * C(k + t - 1, k - 1, fact, invFact) * (n - k - t) % MOD;
						val += add;
						if(val >= MOD) val -= MOD;
					}
				}
				ans += val;
				if(ans >= MOD) ans -= MOD;
			}
		}
	}
	cout << ans;
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 10

热门讨论