题解：P17224 [Math×Girl²] 搬家

bcdmwSjy · 2026-08-09 21:41:20 · 题解

下文表示物品数和容量的 N 和 M 均使用小写字母。

首先我们发现，价值为 3^{n-i} 说明一个物品的价值严格大于后面的物品价值之和，所以最优策略就是按照编号从小到大装。

设有 k 个大小为 1 的物品，有 n-k 个大小为 2 的物品，这里 k 可以枚举。

若 k\ge m，此时打包机会装 m 个 1，我们要保证最优策略不会装入任何 2，最优策略遇到 2 时若容量 \ge2 就会装入，所以要在 2 出现之前让容量 \le1，此时至少装入 m-1 个 1，所以前 m-1 个物品必须是 1，后面 n-m+1 个物品里有一个 1 就行，方案数为 2^{n-m+1}-1，这种情况只需要计算一次。

若 k<m，此时打包机先装入所有 1，还剩下 m-k 的容量，令 h=\left\lfloor\frac{m-k}2\right\rfloor。

• 若 n-k\le h，此时所有物品都能装进去，可以随便分，方案数为 \binom nk。

• 若 n-k>h，此时应该装入 k 个 1 和 h 个该装的 2。

  • 若 (m-k)\bmod2=1，所有的不该装的 2 必须在最后，k 个 1 和 h 个 2 可以任意排列，方案数为 \binom{k+h}k。

  • 若 (m-k)\bmod2=0，除了上面的方案，还可以先放 k-1 个 1 和 h 个该装的 2，再在剩下的 n-k-h 个不该装的 2 中放一个 1（剩余容量为 1，不会装入 2），方案数为 \binom{k+h-1}{k-1}\times(n-k-h)。

预处理阶乘及其逆元后按照上面的式子计算即可，时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr int mod=998244353;

inline ll qpow(ll a,ll b){
    ll res=1;
    for (;b;b>>=1,a=a*a%mod) if (b&1) res=res*a%mod;
    return res;
}

ll inv[10000001],fac[10000001],ifac[10000001];

inline ll C(int n,int m){
    if (n<0 or n<0 or n<m) return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
    for (int i=2;i<=n;i++){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        fac[i]=fac[i-1]*i%mod;
        ifac[i]=ifac[i-1]*inv[i]%mod;
    }
    ll ans=0;
    if (n>=m) ans=(qpow(2,n-m+1)-1+mod)%mod;
    for (int i=0;i<=min(n,m-1);i++){
        int h=(m-i)>>1;
        if (n-i<=h) ans=(ans+C(n,i))%mod;
        else{
            ans=(ans+C(i+h,i))%mod;
            if (((m-i)&1)==0){
                if (i) ans=(ans+C(i+h-1,i-1)*(n-i-h))%mod;
            }
        }
    }
    cout<<ans;
    return 0;
}