P14636 题解
I_will_AKIOI
·
·
题解
补题一小时过了，没有学题解的任何东西，因为我看不懂。
考虑原价不取到最大值的情况。如果一个物品可以取到肯定是最优的，因为性价比从大到小排序。但是如果一个物品没钱买可能就会出现问题。
考虑一种情况：按性价比从大到小选，到一个 w_k=2 的物品 k，刚好剩余一块钱，k 之前最近选了一个 w_i=1 的物品 i，k 之后有一个物品 j 满足 w_j=1 且 w_i+w_j<w_k。物品的性价比从大到小为 i,k,j。
按照小 R 的贪心思路，她会先选择 i。接下来 k 由于需要两块钱，但是只有一块钱没法选，所以小 R 会去选择 j 并把钱花完。但是由于 w_i+w_j<w_k，用 k 替换 i,j 更优，就会导致贪心出错。
既然是由 i,j,k 引起的贪心出错，那么我们枚举他们三个。注意 j 可能没有，可以认为 j=0。
考虑 [1,j-1],[j+1,i-1],[i+1,k-1],[k,n] 这四个区间内的 w 应如何选择。
**上面这行文字是我赛时没有想到的，赛时以为 $[i+1,k-1]$ 之间全是 $2$，`sale2.in` 调了一辈子，宝宝我真糖。好在想错了还有 $m=2$ 的 $20$ 分保底。**
接着对于 $[k,n]$ 之间的物品，还需要花 $m-x-2$ 元（$i$ 性价比比 $k$ 高，会先选择并花费 $1$ 元）。即在 $n-k$ 个物品中，每个物品有 $1/2$ 的权值，问凑出 $m-x-2$ 的方案数。给权值 $-1$，变成 $m-x-2-(n-k)$ 中选择 $n-k$ 个 $1$，答案为 $C_{m-x-2-(n-k)}^{n-k}$。
其他的在图中已经说清楚了，直接按照前文模拟，时间复杂度 $O(Tn^4)$，可以斩获比暴力多过一个测试点 $6$ 的好成绩。
::::info[$O(Tn^4)$ code]
```cpp
ans=Pow(2,n);
for(int k=2;k<=n;k++)
{
for(int i=1;i<k;i++)
{
if(a[i]*2<=a[k]||m-(n-k)<1) continue;
for(int j=0;j<i;j++)
{
if(a[i]+a[j]>=a[k]) continue;
for(int x=0;x<=k-i-1&&m-(n-k)-x>=2;x++)
{
if(m-(n-k)*2-x>2) continue;
ans=(ans-Pow(2,j-1)*C[n-k][m-x-2-(n-k)]*C[k-i-1][x])%mod;
}
}
}
}
```
枚举条件可以不用的，因为不合法的话组合数为 $0$。
::::
发现 $j$ 其实是没用的，唯一用处在于 $2^{j-1}$。双指针一下就可以去掉 $j$ 的枚举，做到 $O(Tn^3)$，理论上 $52$，实测 $92$。
考虑去掉 $x$ 的枚举。如果你打了上周 ABC，会发现 F 题恰好有这个结论。引用一下原题[第一篇题解](https://www.luogu.com.cn/article/nknc86sv)的 Markdown。
:::info[范德蒙德卷积]
$$\sum_{t=0}^{n}\binom{n}{t}\binom{m}{k-t}=\binom{n+m}{k}$$
证明：考虑一共有 $n+m$ 个物品，从中选 $k$ 个。这件事情等价于在 $n$ 个物品中先选 $t$ 个，再在剩下 $m$ 个物品中选 $m-k$ 个。改变的仅仅是枚举顺序。
::::
代入到 $O(Tn^4)$ 的代码中，就是：
```ans=(ans-sum*C[n-j-1][m-2-(n-k)])%mod;```
于是就可以做到 $O(Tn^2)$。
::::info[$O(Tn^2)$ code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define N 5005
using namespace std;
int sub,n,m,ans,a[N],C[N][N];
int Pow(int x,int y)
{
if(y<0) return 0;
int res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
ans=Pow(2,n);
for(int k=2;k<=n;k++)
{
int p=0,sum=1;
for(int j=k-1;j>=1;j--)
{
while(p<n&&a[p+1]<a[k]-a[j]) p++,sum=sum*2%mod;
if(a[j]*2<=a[k]||m-(n-k)<1||a[j]==a[k]) continue;
if(m-2-(n-k)>=0&&m-2-(n-k)<=n-j-1) ans=(ans-sum*C[n-j-1][m-2-(n-k)])%mod;
}
}
ans=(ans+mod)%mod;
cout<<ans<<"\n";
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
C[0][0]=1;
for(int i=1;i<=5000;i++)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
int t;
cin>>sub>>t;
while(t--) solve();
return 0;
}
```
::::
事实上我的赛时：T2 调了三小时，操你妈的世界。