Discovering Paths (UVA 13050) by aizu_f
Contest: 3738    RunID: 20173790    Status: Accepted    Date: Sat Oct 14 14:28:30 JST 2017


#include <bits/stdc++.h>
#include<set>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<stdio.h>
#define INF 100000000
#include<map>
#define P pair<int, int>
#define vector V
using namespace std;

int dp[1002][1002];
int dpp(int i, int j){
	if(i == 0 && j == 0) return 1;
	int &ret = dp[i][j];
	if(ret != -1) return ret;
	ret = 0;
	if(i >= 1) ret += dpp(i - 1, j);
	if(j >= 1) ret += dpp(i, j - 1);
	ret %= 912;
	return ret;
}
int main() {
	memset(dp, -1, sizeof dp);
	int tc, cs = 0;
	scanf("%d", &tc);
	while(tc-- > 0){
		int n, m, q;
		scanf("%d%d%d", &n, &m, &q);
		P ans[n + 1][m + 2];
		for(int i = 0; i <= n- 1; i++){
			for(int j = 0; j <= m - 1; j++){
				int x  = (n - 1) - i - 1;
				int y = m - 1 - j;
				if(x >= 0 && y >= 0){
					ans[i][j].first = (dpp(i, j) * dpp(x, y)) % 912;
				
				}
				x =n - 1 - i;
				y = m - 1 - j - 1;
				if(x >= 0 && y >= 0){
					ans[i][j].second = (dpp(i, j) * dpp(x, y)) % 912;
				
				}
				if(j >= 1){
					ans[i][j].first += ans[i][j - 1].first;
				}
				if(i >= 1) ans[i][j].second += ans[i - 1][j].second;
				ans[i][j].first %= 912; ans[i][j].second %= 912;
			}		
		}
		printf("Case %d\n", ++cs);
		int t = 0;
		while(q--){
			int x, y, x1, y1;
			scanf("%d%d", &x, &y); scanf("%d%d", &x1, &y1);
			int ans1 = 0;
			if(x >= 1) ans1 = (ans[x - 1][m - 1].first - ans[x - 1][y1].first) % 912;
			if(ans1 < 0) ans1 += 912;
			if(y >= 1) ans1 += (ans[n - 1][y - 1].second - ans[x1][y - 1].second) % 912;
			ans1 %= 912;
			if(ans1 < 0) ans1 += 912;
			printf("   Query %d: %d\n", ++t, ans1);
		}
	}
	return 0;
}