Discovering Paths (UVA 13050) by UKUNICHIA
Contest: 3738    RunID: 20174221    Status: Wrong answer    Date: Sat Oct 14 15:37:18 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);}

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 -= dp[getDis(0,0,i,d)][d] * dp[getDis(i,d+1,w-1,h-1)][w-1-i];
	  //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 -=dp[getDis(0,0,c,i)][c] * dp[getDis(c+1,i,w-1,h-1)][h-1-i];
	  //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;
}