Discovering Paths (UVA 13050) by kzyKT
Contest: 3738    RunID: 20174235    Status: Accepted    Date: Sat Oct 14 15:38:30 JST 2017


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=912;
ll d[1111][1111];
int N=1001,M=1001;

int main() {
  d[0][0]=1;
  for(int i=0; i<N+M-1; i++) {
    ll x=max(0,i-M+1),y=min(M-1,i);
    while(x<N) {
      d[x+1][y]+=d[x][y];
      d[x][y+1]+=d[x][y];
      d[x+1][y]%=mod;
      d[x][y+1]%=mod;
      x++;
      y--;
    }
  }
  ll T,tt=1;
  cin >> T;
  while(T--) {
    ll n,m,q,t2=1;
    cin >> n >> m >> q;
    cout << "Case " << tt++ << endl;
    while(q--) {
      ll x1,y1,x2,y2;
      cin >> x1 >> y1 >> x2 >> y2;
      x1--,y1--,x2++,y2++;
      ll ans=0;
      while(x1>=0&&y2<m) {
        ans+=d[x1][y2]*d[n-x1-1][m-y2-1];
        ans%=mod;
        x1--;
        y2++;
      }
      while(x2<n&&y1>=0) {
        ans+=d[x2][y1]*d[n-x2-1][m-y1-1];
        ans%=mod;
        x2++;
        y1--;
      }
      cout << "   Query " << t2++ << ": " << ans << endl;
    }
  }
  return 0;
}