Submission #2549063

---

Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;

int const MAX = 2003;
long long dp1[MAX][MAX], dp2[MAX][MAX], a[MAX];
long long const MOD = 1000000007;

long long mod_plus(long long x, long long y) {
	return (x + y) % MOD;
}
long long mod_mult(long long x, long long y) {
	return (x * y)%MOD;
}

long long f_dp(int i, int j, int type) {
	if (i < 0 || j < 0) { return 0; }
	else if(type == 1){
		return dp1[i][j];
	}
	else {
		return dp2[i][j];
	}
}

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i <= n; i++) {
		dp1[i][0] = 1;
		dp2[i][0] = 1;
	}
	for (int j = 1; j <= m; j++) {
		dp1[0][j] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp1[i][j] = mod_plus(mod_plus( f_dp(i, j - 1, 1), MOD - f_dp(i - 1, j - 1 - a[i], 1)), f_dp(i - 1, j, 1));
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp2[i][j] = mod_plus(mod_plus(f_dp(n, j, 1), MOD - f_dp(n, j - 1, 1)), f_dp(i, j - 1 - a[i], 2));
		}
	}
	for (int i = 0; i < q; i++) {
		int k, x;
		cin >> k >> x;
		cout << f_dp(k, m - x,2) << endl;
	}
}

Submission Info

Judge Result