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

· · 题解

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

关键性质

由于

3^{N-i}>\sum_{j=i+1}^N 3^{N-j}

所以任意一个编号小的物品，其价值大于后面所有物品价值之和。

因此最优解等价于贪心：

按编号从小到大扫描每个物品，如果当前物品能放入剩余容量，就一定要选它；否则跳过。

这就是“能放就放”的贪心。

枚举大小为 1 的物品数量

设共有 c 个物品大小为 1，其余 N-c 个物品大小为 2。

总大小为

c+2(N-c)=2N-c

如果

2N-c\le M

即

c\ge 2N-M

那么所有物品都能被装入箱子，打包机结果和最优解都是全集，方案数为

\binom{N}{c}

下面只考虑总大小大于 M 的情况。

情况一：c\ge M

此时打包机先装大小为 1 的物品。

因为大小为 1 的物品至少有 M 个，所以打包机会按编号顺序装前 M 个大小为 1 的物品，箱子正好装满，不会装任何大小为 2 的物品。

要让贪心最优解也得到同样的结果，必须保证：

前 M-1 个物品全都是大小为 1。

否则，如果前面出现了一个大小为 2 的物品，贪心到它时剩余容量至少为 2，就会选它，与打包机结果不同。

因此方案数为：前 M-1 个位置固定为 1，剩余位置中再选 c-(M-1) 个位置放 1。

\binom{N-M+1}{c-M+1}

情况二：c<M

此时打包机先装完所有大小为 1 的物品。

剩余容量为

R=M-c

设

R=2k+r

其中

k=\left\lfloor \frac{M-c}{2}\right\rfloor,\qquad r=(M-c)\bmod 2

由于总大小大于 M，大小为 2 的物品足够多，所以打包机会按编号顺序装最小的 k 个大小为 2 的物品。

也就是说，打包机选出的集合是：

现在考虑第 k+1 个大小为 2 的物品，它是打包机第一个不选的物品。

设它的位置为 x，在它前面有 A 个大小为 1 的物品。

因为它是第 k+1 个大小为 2 的物品，所以在它前面还有 k 个大小为 2 的物品，所以

x-1=A+k

即

x=A+k+1

在扫描到位置 x 时，剩余容量为

M-A-2k

为了让贪心也不选这个物品，必须有

M-A-2k\le 1

代入 M=c+2k+r，得到

A\ge c+r-1

又因为 A\le c，所以 A 只有一两个取值：

对于每个合法的 A：

\binom{A+k}{A} \binom{N-A-k-1}{c-A}

所以该部分贡献为

\binom{A+k}{A} \binom{N-A-k-1}{c-A}

时间复杂度

预处理阶乘和逆元，O(N)。

枚举 c=0,1,\dots,N，每次 O(1) 计算组合数，总复杂度 O(N)。

对于 N\le 10^7 是可行的。

#include<bits/stdc++.h>
using namespace std;
using int64=long long;
const int MOD=998244353;
int mod_pow(int64 a,int64 e){
    int64 r=1;
    while(e){
        if(e&1)r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return(int)r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin>>N>>M;
    vector<int>fact(N+1),inv_fact(N+1);
    fact[0]=1;
    for(int i=1;i<=N;i++)fact[i]=(int64)fact[i-1]*i%MOD;
    inv_fact[N]=mod_pow(fact[N],MOD-2);
    for(int i=N;i>=1;i--)inv_fact[i-1]=(int64)inv_fact[i]*i%MOD;
    auto C=[&](int n,int k)->int{
        if(k<0||k>n||n<0)return 0;
        return (int64)fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD;
    };
    int ans=0;
    int limit_total=2*N-M;
    for(int c=0;c<=N;c++){
        if(c>=limit_total){
            ans=(ans+C(N,c))%MOD;
        }else{
            if(c>=M){
                if(M<=N){
                    ans=(ans+C(N-M+1,c-M+1))%MOD;
                }
            }else{
                int rem=M-c;
                int r=rem&1;
                int k=(rem-r)/2;
                for(int A=c+r-1;A<=c;A++){
                    if(A<0)continue;
                    int term=(int64)C(A+k,A)*C(N-A-k-1,c-A)%MOD;
                    ans=(ans+term)%MOD;
                }
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}