我也就只能会这种简单组合题了

· · 题解

歌挺好听的。

为了说明方便，我们用“数”表示“物品”，“1”“2”表示“大小为 1 的物品”“大小为 2 的物品”，“前面”“后面”表示“编号更小”“编号更大”，“选”表示“装”。

首先理解题意，这种选的方式会使所有的 1 替换为其他 1，2 替换为其他 2 的操作都不优，又由于能够选 2 仅当 1 已经选完，我们只需要考虑 1 替换为 2 的情况是否可能更优。

设 1 共有 i 个，我们枚举 i。

对于 i=0，仅有一种方案，显然最优；对于 1\le i\le N，我们分成两部分考虑。

如果 i<M，那么一定会把所有 1 都选掉，也就是没选的只有 2。此时我们再分类讨论：

若我们可以把所有数选掉，即 i+2(N-i)\le M，那么所有情况都是最优解，方案数为 \binom{N}{i}。

若我们不能选掉所有数，且 i 与 M 奇偶性相反，那么最终打包机会剩余 1 的容量，我们可以将任意一个 1 替换为一个没有选的 2。为了使这种操作不使价值更大，最终我们选的数一定是前面连续的一段，和为 M-1，所以有 \frac{M-1-i}{2} 个 2，方案数为 \binom{i+\frac{M-1-i}{2}}{i}。

若我们不能选掉所有数，且 i 与 M 奇偶性相同，那么最终打包机会选满，我们可以将任意两个 1 替换为一个没有选的 2。显然前面一种情况的选数方法也是适用的，方案数为 \binom{i+\frac{M-i}{2}}{i}。除此之外我们发现，仅有一个 1 在某些没有选的 2 后面也是可以的，此时前面连续的一段是 i-1 个 1 和 \frac{M-i}{2} 个 2，后面接一个 2，再后面的 N-i-\frac{M-i}{2} 个数中有一个 1，方案数为 (N-i-\frac{M-i}{2})\binom{i-1+\frac{M-i}{2}}{i-1}。

如果 i\ge M，则会全部都选 1，同样可以把任意两个 1 替换为一个 2，因此最多只有一个 1 在某些 2 后面。也就是前面 M-1 个都是 1，剩下的除了不能全是 2 以外任意，方案数为 2^{N-M+1}-1。

于是这题就分讨完了。

写的时候稍微注意一下边界，阶乘和阶乘逆元预处理一下。

不知道为什么我又想放代码了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
#define N 10000010
int n,m,f[N],inv[N],ans=1;
int qp(int a,int b){
    int res=1;
    while(b){
        if(b&1)(res*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return res;
}
int C(int a,int b){
    return f[a]*inv[b]%mod*inv[a-b]%mod;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i%mod;
    inv[n]=qp(f[n],mod-2);
    for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<m&&i<=n;i++)
        if(i+(n-i)*2<=m)(ans+=C(n,i))%=mod;
        else if((m+i)%2)
            (ans+=C((m+i-1)/2,i))%=mod;
        else{
            (ans+=C((m+i)/2,i))%=mod;
            (ans+=C((m+i)/2-1,i-1)*(n-(m+i)/2))%=mod;
        }
    if(m<=n)(ans+=qp(2,n-m+1)-1)%=mod;
    cout<<ans<<'\n';
    return 0;
}