Submission #123615

---

Source Code Expand

// compile with "g++ XXX.cc -mno-cygwin -O2" in Cygwin

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>
#include<bitset>
#include<cassert>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define FOR3(i,a,b) for(int i=a,i##_end=b;i<i##_end;i++)
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define CLS(x,val) memset((x) , val , sizeof(x)) 
typedef long long ll_t;
typedef long double ld_t;
typedef vector<int> VI; 
typedef vector<VI> VVI;
typedef complex<int> xy_t;

template<typename T> void debug(T v , string delimiter = "\n")
{ for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++) cout << *it << delimiter; cout << flush ;}

int dx[]  = {0,1,0,-1};
int dy[]  = {1,0,-1,0};
string ds = "SENW";

const double PI = 4.0*atan(1.0);

const int mod = 1000000000 + 7;

long long choose[1000][1000];

int main() {
  FOR(i,1000) FOR(j,1000) {
    if(i < j) choose[i][j] = 0;
    else {
      if(i == j || j == 0) {
        choose[i][j] = 1;
      }else {
        choose[i][j] = (choose[i-1][j-1] + choose[i-1][j]) % mod;
      }
    }
  }

  long long W,H,X,Y,D,L;
  cin>>W>>H>>X>>Y>>D>>L;

  long long ans = 0;  
    int all = D + L;
    long long placePattern = (W - X + 1) * (H - Y + 1) % mod;
  long long pre = 0 ;
  long long dp2[1000];
  for(int y = 1; y <= Y ; y++){
    long long dp[100][1000];
    memset(dp , 0 , sizeof(dp));
    dp[0][all] = 1;
    FOR(i,X) {
      for(int j=0;j<=all;j++) {
        for(int k=0;k<=j;k++) {
          int placed = j - k;
          if(i == 0 && placed == 0) continue;
          if(placed > y) continue;
          if(i == X - 1 && placed == 0) continue;
          dp[i+1][k] += dp[i][j] * choose[y][placed];
          dp[i+1][k] %= mod;
        }
      }
      //FOR(j,all+1) cout<<" "<<dp[i+1][j]; cout<<endl;
    }
    long long pattern = dp[X][0] ;
    long long just = pattern;
    for(int y2=1;y2<y;y2++){
      just -= (dp2[y2] * (y - y2 + 1)) % mod;
      just = (just + mod) % mod;
    }
    dp2[y] = just;
    
    pre += pattern;
    pre %= mod;
    if(y == Y){
      ans += just;
      ans %= mod;
    }
  }
  ans = (ans * placePattern) % mod;
  ans = (ans * choose[all][D]) % mod;

  cout<<ans<<endl;

  return 0 ;
}

Submission Info

Judge Result