蒟蒻第一次写绿题题解（能写出来就是个奇迹了，版面设计上不要有太大要求，如有错误请大佬们指出，只要还没AFO呢就一定会尽快改正），走过路过还望大佬们点个关注留个赞（第一次用acgo，简直弱爆了awa）
P17224 [MATH×GIRL²] 搬家
题目传送门
题目描述
小魔女 A 和小魔女 S 有一个容量为 MMM 的箱子和 NNN 个物品。
物品按 111 到 NNN 编号，第 iii 个物品的价值为 3N−i3^{N-i}3N−i。
小魔女 A 可以决定每个物品的大小：令其为 111 或 222。
小魔女 S 使用一个打包机，该打包机的装填策略如下：
1. 优先装大小为 111 的物品：在大小为 111 的物品中，按编号从小到大依次尝试装入，直到箱子装满或所有大小为 111 的物品都被装入。
2. 再装大小为 222 的物品：若还有剩余容量，在大小为 222 的物品中，按编号从小到大依次尝试装入，直到箱子装满或所有大小为 222 的物品都被装入。
小魔女 S 希望装入物品的总价值最大。如果打包机的结果不是最优解，她会手动调整为最优解。
她不知道小魔女 A 要怎么设定物品大小，所以她想知道有多少种给物品分配大小的方案，使她无需手动调整？
答案对 998244353998244353998244353 取模。
输入格式
一行两个正整数 N,MN,MN,M。
输出格式
一行一个整数，表示方案数对 998244353998244353998244353 取模后的结果。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
输入输出样例 #3
输入 #3
输出 #3
说明/提示
样例解释
对样例 #1：有 22=42^2=422=4 种分配方案。
物品大小 打包机装入的物品 最优方案 1,11,11,1 {1,2}\{1,2\}{1,2} {1,2}\{1,2\}{1,2} 1,21,21,2 {1}\{1\}{1} {1}\{1\}{1} 2,12,12,1 {2}\{2\}{2} {1}\{1\}{1} 2,22,22,2 {1}\{1\}{1} {1}\{1\}{1}
共有 333 种方案符合要求。
数据范围与约定
本题开启捆绑测试。
子任务 分值 N,M≤N,M\leN,M≤ 特殊性质 111 101010 10710^7107 M≥2NM\ge2NM≥2N 222 202020 101010 - 333 303030 500050005000 444 404040 10710^7107
对于 100%100\%100% 的数据，1≤N,M≤1071 \le N, M \le 10^71≤N,M≤107。
数学原理
根据第 i 个物品的价值为 3𝑁−𝑖3^𝑁−𝑖3N−i，可知任意一个物品价值大于其后面所有物品价值之和。
N=4时
i 1 2 3 4 3N−13^{N-1}3N−1 34−13^{4-1}34−1 34−23^{4-2}34−2 34−33^{4-3}34−3 34−43^{4-4}34−4 对应数值 27 9 3 1
贪心策略：尽量拿编号小的物品，直到装满容量 𝑀。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
分情况讨论
情况 1：𝑀 ≥ 𝟐𝑵
这说明箱子总容量足够放下全部物品（所有物品就算全是 2，也能全部放下）
无论打包机怎么分配大小，也全能装进去，即等于最优解。
总方案数：2N mod 9982443532 ^ N\bmod9982443532Nmod998244353
情况 2：𝑀 < 𝟐𝑵
此时箱子不能放下所有的物品。
设 𝑘 为大小为 1 的物品总个数
情况 2.1：𝑘 ≥ 𝑀
大小为 1 的物品数量超过箱子容量，打包机出来后直接装入前 𝑀 个大小为 1 的物品。
后面的 𝑁 − 𝑀 个物品任意打包成大小 1 或大小 2。
则 打包结果 = 最优解
当大小为 1 的物品足够多时（𝑘 ≥ 𝑀），打包机只选大小为 1 的物品，不选择任何大小为 2 的品。
必须保证在装满之前，绝不会遇到任何一个大小为 2 的物品。
前 𝑀 − 1 个物品大小必须全为 1。
前 𝑀 − 1 个位置固定后，还剩下 𝑁 − 𝑀 + 1 个位置。这里必须至少有一个大小为 1，不能全为 2。
总方案数：𝟐𝑵−𝑴+𝟏−𝟏𝟐 ^ 𝑵−𝑴+𝟏 − 𝟏2N−M+1−1
情况 2.2：𝑘 < 𝑀
此时大小为 1 的物品只有 𝑘 个，打包机会先把这 𝑘 个 1 全部装入，剩余容量为：
𝑅=𝑀−𝑘𝑅 = 𝑀 − 𝑘 R=M−k
还能装大小为 2 的物品，最多能装：
𝑡=⌊𝑅2⌋𝑡 = \lfloor \frac{𝑅}{2} \rfloor t=⌊2R ⌋
打包机选择的是：所有编号最小的 𝑡 个大小为 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_𝑡21 ,22 ,⋯,2t ，那么最
优解扫描到这 𝑘 + 𝑡 个物品时，箱子正好装满（因为总大小为 𝑘 + 2𝑡 = 𝑀 − 1，，离满还差
1），遇到后面的 2 时只剩 1 容量，装不下。
这 𝑘 + 𝑡 个物品的排列中，只需要决定哪些位置放 1（其余放那 t 个特定的 2），
方案数为：
(k+tk)\binom{k + t}{k} (kk+t )
情况 2.2.2：𝑅 为偶数
打包机装完 k 个 1 和 t 个 2 后，箱子刚好装满（容量为 0）。
有效情况分两种（避免重复计数）：
1. 基础情况：
前 𝑘 + 𝑡 个物品包含全部 k 个 1 和 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡21 ,22 ,⋯,2t 。
最优解扫完这 𝑘 + 𝑡 个物品后容量为 0。
基础方案数为：
(k+tk)\binom{k + t}{k} (kk+t )
2. 额外情况
如果前 𝑘 + 𝑡 − 1 个物品只包含 𝑘 − 1 个 1 和 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡21 ,22 ,⋯,2t ，还剩下 1 个 1 没有出现。
此时，最优解扫完这 𝑘 + 𝑡 − 1 个物品后，剩余容量为 1，（因为总大小为 (𝑘 − 1) + 2𝑡 = 𝑀 − 1）。
它遇到后面的 2𝑡+1 时，因为容量只有 1，装不下它，只能继续往后扫描，直到遇到那最后
一个 1，把它装进去，箱子才正好装满。
为了保证不重复基础情况，最后一个 1 必须出现在第 𝑘 + 𝑡 个位置之后：
前 𝑘 + 𝑡 − 1 个位置中，选 𝑘 − 1 个放放 1，其余放 21,22,⋯ ,2𝑡2_1, 2_2,\cdots , 2_𝑡21 ,22 ,⋯,2t ：有 (k+t−1k−1)\binom{k + t - 1}{k - 1}(k−1k+t−1 ) 种；
剩下的那一个 1，可以放在位置 𝑘 + 𝑡 + 1 到 𝑁 之之间的 任意位置 ，只要它后面全是未被选中的 2。
𝑁−(𝑘+𝑡+1)+1=𝑁−𝑘−𝑡𝑁 − (𝑘 + 𝑡 + 1) + 1 = 𝑁 − 𝑘 − 𝑡 N−(k+t+1)+1=N−k−t
额外方案数为：
(k+t−1k−1)×(N−k−t)\binom{k + t - 1}{k - 1} \times (N - k - t) (k−1k+t−1 )×(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) (kk+t )+(k−1k+t−1 )×(N−k−t)
参考代码：
