Discovering Paths (UVA 13050) by UKUNICHIA
Contest: 3738    RunID: 20174242    Status: Wrong answer    Date: Sat Oct 14 15:39:47 JST 2017


#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#define MAX_P 2020
Int dp[MAX_P][MAX_P];
void init(Int p){
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(Int i=1;i<MAX_P;i++){
    for(Int j=0;j<=i;j++){
      dp[i][j]=dp[i-1][j];
      if(j) dp[i][j]+=dp[i-1][j-1];
      dp[i][j]%=p;
    }
  }
}

Int getDis(Int a,Int b,Int c,Int d){return abs(a-c) + abs(b-d);}
const int mod = 912;
signed main(){
  init(912);
  Int T;
  cin>>T;
  for(Int t=1;t<=T;t++){
    cout<<"Case "<<t<<endl;
    Int w,h,Q;
    cin>>w>>h>>Q;

    for(Int q=1;q<=Q;q++){
      Int a,b,c,d;
      cin>>a>>b>>c>>d;

      Int ans = dp[getDis(0,0,w-1,h-1)][w-1];
      //cout<<ans<<endl;
      for(Int i=a;i<=c;i++) if(i+1<h) {
	  ans = (ans + mod - dp[getDis(0,0,i,d)][d] * dp[getDis(i,d+1,w-1,h-1)][w-1-i]%mod)%mod;
	  //cout<<getDis(0,0,i,d)<<" "<<d<<":"<<getDis(i,d+1,w-1,h-1)<<" "<<w-1-i<<endl;
	  //cout<<dp[getDis(0,0,i,d)][d]<<" "<<dp[getDis(i,d+1,w-1,h-1)][w-1-i]<<endl;
	}
      for(Int i=b;i<=d;i++) if(i+1<w) {
	  ans = (ans+ mod -dp[getDis(0,0,c,i)][c] * dp[getDis(c+1,i,w-1,h-1)][h-1-i]%mod)%mod;
	  //cout<<dp[getDis(0,0,c,i)][c]<<" "<<dp[getDis(c+1,i,w-1,h-1)][h-1-i]<<endl;
	}
      cout<<"   Query "<<q<<": "<<ans<<endl;
    }
      
    
    
  }
  
  
  return 0;
}