本文迁移自洛谷原文。
link
题目大意：
给定 ，。有 种商品，编号从 到 ，第 种商品最多能拿 个。
共 次询问。每次询问给定 ，，求第 种商品 恰好 拿走 个的前提下，在 种商品中一共拿走 个商品的方案数。两种方案不同当且仅当存在一种商品在二方案中被拿走的个数不同。输出答案对 取模的结果。
部分分是 和 。
题解：
部分分是基础 。
令 表示考虑到第 种物品，当前已经选了 个时的方案数。转移为 。
然后每次询问暴力求一遍 dp，可以拿到第一个部分分。
然后我们可以发现第二个部分分中 小 大，就可以考虑预处理出所有询问要恰好拿走的商品 id 做最后一个物品的 dp 数组（很容易发现这些商品之间的顺序无关紧要），就可以了。预处理复杂度 。
正解还是要看到这个商品之间的顺序无关紧要。
再观察这个转移式子，。
考虑反过来由 推向 ，会有什么效果？
相当于 再加上 （如果 ）。
再根据商品之间无关紧要， 这个数组为考虑完全部的 个物品之后得到的 dp 值，前面商品的顺序再怎么换也不会影响到它，所以我们可以枚举假设最后一个选的是 号物品， 的倒推即可。总时间复杂度 。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
const int mxn=2005;
const int md=1000000007;
inline void add(int&x,int y){
x+=y;
if(x>=md)x-=md;
}
inline void del(int&x,int y){
x-=y;
if(x<0)x+=md;
}
int n,m,q,a[mxn],f[mxn][mxn],g[mxn][mxn];
int main(){
ios_base::sync_with_stdio(false);
cin>>n>>m>>q;for(int i=1;i<=n;++i)cin>>a[i];
f[1][0]=1;
for(int i=1;i<=n;++i){
int t=0;
for(int j=0;j<=m*2;++j){
add(t,f[i][j]);
if(j>a[i])del(t,f[i][j-a[i]-1]);
f[i+1][j]=t;
}
}
for(int i=1;i<=n;++i){
g[i][0]=1;
for(int j=1;j<=m;++j){
g[i][j]=(f[n+1][j]-f[n+1][j-1]+md)%md;
if(j>a[i])add(g[i][j],g[i][j-a[i]-1]);
}
}
for(;q--;){
int x,k;cin>>x>>k;
if(k>m)cout<<0<<'\n';
else cout<<g[x][m-k]<<'\n';
}
}
|