题目
题目链接：https://www.luogu.com.cn/problem/U142633
有 (m) 个物品，第 (i) 个物品有两个参数 (a_i,b_i)，将这 (n) 个物品放进 (m) 个格子中，如果第 (i) 个物品放了 (p_i) 个，那么这种放置方法的价值为
[Pi^{n}_{i=1}(a_ip_i^2+b_ip_i+1)
]
两种方案不同当且仅当存在一个物品放置数量不同，求所有放置方案的价值之和。(Q) 组询问，但 (m) 相同。
(m,Qleq 10^3;nleq 10^4;a_i,b_ileq 10^9)。
思路
设 (f[i][j]) 表示前 (i) 个格子放了 (j) 个物品的价值。那么显然有转移
[f[i][j]=sum^{i}_{k=1}f[i-k][j-1](a_ik^2+b_ik+1)
]
直接转移是 (O(n^2m)) 的。考虑优化。
考虑 (f[i][j]) 可以转移到什么状态，有
[f[i+k][j+1]gets f[i][j](a_{i+1}k^2+b_{i+1}k+1)
]
[f[i+k][j+1]gets f[i][j]·a_{i+1}k^2+f[i][j]·b_{i+1}k+f[i][j]
]
可以将右边三个单项式分别计算出来然后求和。
对于 (f[i][j])，直接将 (sum0[i]) 加 (f[i][j])，然后做一遍前缀和。
对于 (f[i][j]·b_{i+1}k)，将 (sum1[i]) 加 (f[i][j]·b_{i+1})，然后做两遍前缀和。
对于 (f[i][j]·a_{i+1}k^2)，将 (sum2[i]) 和 (sum2[i+1]) 加 (f[i][j]·b_{i+1})，然后做三遍前缀和。
此时每一个数组存的就是答案了。再跑一遍赋值即可。
时间复杂度 (O(nm))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10010,M=1010,MOD=998244353;
int Q,n,m,sum0[N],sum1[N],sum2[N],a[M],b[M],f[N][M];
int main()
{
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&a[i],&b[i]);
f[0][0]=1;
for (int j=0;j<m;j++)
{
memset(sum0,0,sizeof(sum0));
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
for (int i=0;i<N;i++)
{
sum0[i]=(sum0[i]+f[i][j])%MOD;
sum1[i+1]=(sum1[i+1]+1LL*f[i][j]*b[j+1])%MOD;
sum2[i+1]=(sum2[i+1]+1LL*f[i][j]*a[j+1])%MOD;
sum2[i+2]=(sum2[i+2]+1LL*f[i][j]*a[j+1])%MOD;
}
for (int i=1;i<N;i++) sum0[i]=(sum0[i]+sum0[i-1])%MOD;
for (int i=1;i<N;i++) sum1[i]=(sum1[i]+sum1[i-1])%MOD;
for (int i=1;i<N;i++) sum1[i]=(sum1[i]+sum1[i-1])%MOD;
for (int i=1;i<N;i++) sum2[i]=(sum2[i]+sum2[i-1])%MOD;
for (int i=1;i<N;i++) sum2[i]=(sum2[i]+sum2[i-1])%MOD;
for (int i=1;i<N;i++) sum2[i]=(sum2[i]+sum2[i-1])%MOD;
for (int i=0;i<N;i++)
f[i][j+1]=(1LL*sum0[i]+sum1[i]+sum2[i])%MOD;
}
scanf("%d",&Q);
while (Q--)
{
scanf("%d",&n);
printf("%d
",f[n][m]);
}
return 0;
}