[Math×Girl²] 搬家

· · 题解

第 i 个物品价值为 3^{N-i}，超过所有编号更大的物品的价值之和，故最优策略按编号从小到大贪即可。

考虑什么时候打包机的方案不是最优的：打包机方案不是最优，即存在可以通过改变更大编号的选择使得较小的编号被选。这只能是打包机的方案恰好使得箱子容量剩余 1 且存在一个未被选择的（未被选择均指未被打包机的方案选择）大小为 2 的物品，有至少一个编号大于它的且被选择的大小为 1 的物品，或者打包机的方案恰好使得箱子容量用尽且存在一个未被选择的大小为 2 的物品，有至少两个编号大于它的且被选择的大小为 1 的物品。

下面考虑合法情况，分为两大类。

第一类：对于第一个未被选择的 2，编号为 d，有以下两种情况：

  1. 若存在编号 \lt d 的物品大小为 2，那么其必然被打包机选中，进而大小为 1 的物品必然全被选中，于是编号 \lt d 的物品全被选中且编号 \gt d 的物品中大小为 1 的物品全被选中；
  2. 若不存在编号 \lt d 的物品大小为 2，也即不存在大小为 2 的物品被选中，这当且仅当 M\le N 时可能发生。

对于这两种情况重新按照编号 \lt d 的物品是否全部被打包机选中重新分类计数，此时只有 M\lt N（此处不取等）需要额外计算。

第二类：若第一个未被选择的 2 不存在，有以下两种情况：

  1. 所有物品大小均为 1；
  2. 箱子足以容纳所有的物品。

当 M\ge N 时，第一种情况被第二种情况包含，无需计入；当 M\lt N 时，两种情况都需讨论。

对于第一类中所有编号 \le d 的物品均被选中的情况，记前面选中了 i=d-1 个物品，分为箱子容量剩余 1 且未被选择的 2 后均为 2，箱子容量剩余 0 且未被选择的 2 后均为 2，箱子容量剩余 0 且未被选择的 2 后恰有 1 个 1 三种情况。其中第一种和第三种编号 \le d 的物品容量和均为 M-1，那么前 i 个物品的大小分配方案共计 \binom{i}{M-i-1}，后 N-i-1 个物品大小分配方案共有 N-i-1+1=N-i 种；第二种物品容量和为 M ，那么前 i 个物品的大小分配方案共计 \binom{i}{M-i} 种。对 i 求和可得第一类的合法方案数共有

\sum_{i=0}^{n-1} \left((N-i)\binom{i}{M-1-i} + \binom{i}{M-i}\right)

对于第二类中箱子足以容纳所有物品的情况，显然合法方案数共有

\sum_{i=n}^{m} \binom{N}{i-N}

对于 M<N 的情况，注意到存在以下情况：

  1. 前 M 个均为 1，后面部分任意，这是对于第一类以及第二类的全部大小均为 1 的补充，合计 2^{N-M} 种；
  2. 前 M-1 个中恰有一个为 2，第 M 个及以后均为 2，这一部分原本应为第一部分 i=M 时的情况中箱子容量剩余 0 的子情况，合计 M-1 种；
  3. 前 M-1 个均为 1，第 M 个为 2，后面部分任意，合计 2^{N-M} 种。

这三种情况恰好能覆盖 i\ge M-1 时的第一类，共有

2\times 2^{N-M}+M-1

同时对于 M<N 的情况第一类的求和上界应调整到 M-2。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
long long frac[10000007],inv[10000007];
const long long mod=998244353,e7=1e7;
long long binom(long long n,long long m){
    if(m>n||m<0)return 0;
    return frac[n]*inv[m]%mod*inv[n-m]%mod;
}
long long quickpow(long long a,long long b){
    long long ans=1;
    long long base=a;
    while(b){
        if(b&1)ans*=base,ans%=mod;
        base*=base,base%=mod;
        b>>=1;
    }
    return ans;
}
long long ans=0,n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    m=min(m,2*n);
    frac[0]=inv[0]=1;
    for(int i=1;i<=e7;++i) frac[i]=i*frac[i-1]%mod;
    inv[e7]=quickpow(frac[e7],mod-2);
    for(int i=e7-1;i>0;--i) inv[i]=inv[i+1]*(i+1)%mod;
    int t=(m<n?m-2:n-1);
    for(int i=0;i<=t;++i){//PART 1
        long long tmp=binom(i,m-1-i)*(n-i)%mod+binom(i,m-i);
        ans+=tmp;
        ans%=mod;
    }
    for(int i=n;i<=m;++i){//PART 2
        long long tmp=binom(n,i-n);
        ans+=tmp;
        ans%=mod;
    }
    if(m<n){//M<N
        ans+=2*quickpow(2,n-m)+m-1;
        ans%=mod;
    }
    printf("%lld",ans);
    return 0;
}

:::