【玫瑰】

WeWantToRun · 2024-08-22 17:54:44 · 题解

讲个笑话：我看完所有题解加上网上搜索硬是没学会前缀和优化多重背包计数。

于是我想了一个小时才会。

显然平均数左右一正一负本质相同，于是问题转化成 1\sim i 每个数 k 个，总和等于 j 的方案数计数，最后答案就是 (k+1)\sum _j f_{x-1,j}f_{n-x,j}-1。

然后大力求这个 f_{i,j} 显然是 O(n^5) 带一个几十分之一的常数，运气好就过去了。然后考虑转移是 f_{i,j}=\sum _{t\le k}f_{i-1,j-ti}，所以考虑把 f 当成 i 个数组，每个数组分别做前缀和，然后就可以 O(1) 转移，时间复杂度 O(n^4)。