ARC028D

ARC028D.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define nil -1
typedef long long ll;

using namespace std;

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << fixed << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

// end of template

int main() {
    cin.tie(0);
    
    // source code
    int N, M, Q;
    cin >> N >> M >> Q; // 商品の種類 2000, 選ぶ商品の個数 2000, クエリの数 500000
    
    vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0)); // dp[x][y] x: 商品の種類 y: 商品の個数
    
    vector<int> A(N);
    rep(i, N){
        cin >> A[i];
    }
    
    dp[0][0] = 1;
    
    // 普通のDP
    rep(i, N){
        dp[i + 1][0] = 1;
        repd(j, 1, M + 1){
            dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j] - (j >= A[i] + 1 ? dp[i][j - A[i] - 1] : 0);
            dp[i + 1][j] = ((dp[i + 1][j] % mod) + mod) % mod;
        }
    }
    
    // 戻すDP
    vector<vector<int>> revdp(N, vector<int>(M + 1, 0)); // i-1行目: i番目を除いた時 これをみてO(1)でクエリに答える
    
    rep(i, N){
        revdp[i][0] = 1;
        repd(j, 1, M + 1){
            revdp[i][j] = dp[N][j] - dp[N][j - 1] + (j >= A[i] + 1 ? revdp[i][j - A[i] - 1] : 0);
            revdp[i][j] = ((revdp[i][j] % mod) + mod) % mod;
        }
    }
    
    rep(i, Q){
        int k, x; // k種類目の商品をちょうどx個選ぶ
        cin >> k >> x;
        output(revdp[k - 1][M - x], 0);
    }
    
    return 0;
}