Discovering Paths (UVA 13050) by ynu_a
Contest: 3738    RunID: 20174924    Status: Wrong answer    Date: Sat Oct 14 17:38:07 JST 2017


#include<bits/stdc++.h>
using namespace std;

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define MOD 912

typedef long long ll;
typedef pair<int, int> ii;

int main(){

  int t;
  cin >> t;
  rep(n, t){
    int R, C, Q;
    cin >> R >> C >> Q;
    vector<vector<int>> dp(R, vector<int>(C, 0));
    dp[0][0] = 1;
    rep(i, R){
      rep(j, C){
        if(i > 0) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
        if(j > 0) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
      }
    }

    cout << "Case " << n+1 << endl;
    rep(q, Q){
      int a, b, c, d;
      cin >> a >> b >> c >> d;

      int ans = dp[R-1][C-1];
      if(a != 0) REP(i, b, d+1){
        ans = (ans + MOD - dp[a-1][i] * dp[R-1-a][C-1-i]) % MOD;
      }
      if(b != 0) REP(i, a, c+1){
        ans = (ans + MOD - dp[i][b-1] * dp[R-1-i][C-1-b]) % MOD;
      }
      cout << "   Query " << q+1 << ": " << ans << endl;
    }

  }

  return 0;
}