题目意思
原题面
高橋商店では \(N\) 種類の商品が売られています。「どの種類の商品がいくつあるか」の情報が与えられるので、「合計 \(M\) 個の商品を選ぶ方法」の数を求めて下さい。ただし、同じ種類の商品は区別しないこととします。
いや、これは少し簡単過ぎるので、ちょっとした注文も追加しよう。整数 k, x からなる \(Q\) 個の注文を用意したので、それぞれについて「\(k_i\) 種類目の商品をちょうど \(x_i\) 個選ばなければならないとき、合計 \(M\) 個の商品を選ぶ方法」の数を求めて下さい。
DeepL 翻译后的题面
高桥商店出售 \(N\) 种类型的商品。 给出 "有多少种产品可供选择 "的信息，找出 "选择总共M种产品的方法 "的数量。 然而，我们将不对同一类型的产品进行区分。
不，这有点太容易了，所以让我们增加一个小订单。 我们有 \(Q\) 个由整数 \(k\) 和 \(x\) 组成的订单。对于每一个订单，请找出 "当正好要选择第 \(k_i\) 种产品的 \(x_i\) 个产品时，总共要选择 \(M\) 个产品的方法 "的数目。
数据范围
商品的种类个数：\(a_i\)，\(k_i\le M\)，\(x_i\le a_{x_i}\)。
-
\(10\%\) 的数据，\(N,M,Q \le 100\)
-
\(30\%\) 的数据，\(N,M\le 100,Q\le 5\cdot 10^5\)
-
\(80\%\) 的数据，\(N,M\le 2000,Q\le 1000\)
-
\(100\%\) 的数据，\(N,M\le 2000,Q\le 5\cdot 10^5\)
解题
方法 \(1\)
我们可以每一次询问单独做一个 dp。设计 \(dp_{i,j}\) 为到了第 \(i\) 种商品，已经选了 \(j\) 个的方案数。转移为 \(\displaystyle dp_{i,j}=\sum^{j}_{k=\max(0,j-a_i)} dp_{i-1,k}\)。保存前缀和，更新的时候就可以 \(O(1)\)。总复杂度 \(O(NMQ)\)。
期望得分 \(10\%\)。
方法 \(2\)
发现如果 \(x_i\) 不会对答案做贡献，可以预处理，枚举每一个 \(i\le N\)，对于每一个除了 \(i\) 的做 dp。这样时间复杂度 \(O(N^2M)\)。
期望得分 \(30\%\)。
方法 \(3\)
发现每一次都重新计算一遍非常的麻烦，也很费时。
其实第 \(i\) 次也就是 \(i\) 影响了，那么 \(0\sim i\) 以及 \(i+1\sim N\) 其实是不需要重新计算的。这样维护两个 dp，一个前缀，一个后缀就可以了，每一次询问 \(O(M)\)，总时间复杂度 \(O(QM+NM)\)。
期望得分 \(80\%\)。
方法 \(4\)
我们先用 「方法 \(1\)」里的 dp 计算一次，设答案数组为 \(dp\)。
定义 \(ans_{i,j}\) 为除了第 \(i\) 种选 \(j\) 个的方法数。很容易发现每一次询问要求的就是 \(ans_{k_i,m-x_i}\)。
\(ans\) 数组的转移为：\(ans_{i,j}=dp_{n,j}-\displaystyle \sum^{j-1}_{k=\max(0,j-a_i)} ans_{i,k}\)。这个式子很好理解。\(dp_{n,j}\) 多考虑了一些方案，就是选取了一些第 \(i\) 种的，这些需要减去。假设选了 \(k\) 个第 \(i\) 种，那么就还要选 \(j-k\) 个不是第 \(i\) 种的，也就是 \(ans_{i,j-k}\)，于是就有了 \(\displaystyle \sum^{j-1}_{k=\max(0,j-a_i)} ans_{i,k}\)。
上面式子里的 \(\displaystyle \sum^{j-1}_{k=\max(0,j-a_i)} ans_{i,k}\) 可以用前缀和处理。复杂度 \(O(NM)\)。
期望得分 \(100\%\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define dg(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 2e3+3;
const int mod = 1e9+7;
ll n,m,q,a[N];
ll dp[N][N],ans[N][N],pre[N];
ll cal(int i){
if (i<0){
return 0;
}
return pre[i];
}
void precalc(){
dp[0][0]=1;
for (int i=0; i<=m; i++){
pre[i]=1;
}
for (int i=1; i<=n; i++){
for (int j=0; j<=m; j++){
dp[i][j]=pre[j]-cal(j-a[i]-1);
dp[i][j]=(dp[i][j]+mod)%mod;
}
pre[0]=dp[i][0];
for (int j=1; j<=m; j++){
pre[j]=pre[j-1]+dp[i][j];
pre[j]%=mod;
}
}
}
void anscalc(){
for (int i=1; i<=n; i++){
for (int j=0; j<=m; j++){
pre[j]=0;
}
ans[i][0]=pre[0]=1;
for (int j=1; j<=m; j++){
ll interval_sum=(pre[j-1]-cal(j-a[i]-1)+mod)%mod;
ans[i][j]=(dp[n][j]-interval_sum+mod)%mod;
pre[j]=pre[j-1]+ans[i][j];
pre[j]%=mod;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>q;
for (int i=1; i<=n; i++){
cin>>a[i];
}
precalc();
anscalc();
while (q--){
int k,x;
cin>>k>>x;
cout<<ans[k][m-x]<<endl;
}
return 0;
}