Submission #1256442
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=n-1;i>=(0);i--) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; int R, C; int X, Y; int D, L; const int MAX_N = 2000; ll inv[MAX_N + 10]; ll fac[MAX_N + 10], facInv[MAX_N + 10]; class MATH{ public: MATH(){ inverse(); factroial(); } ll nCk(ll n, ll k){// n! / k!*(n-k)! if(k < 0 || k > n) return 0; ll ret = fac[n]; (ret *= facInv[k]) %= MOD; (ret *= facInv[n - k]) %= MOD; return ret; } ll nHk(ll n, ll k){// nHk = n+k-1 C k = (n+k-1)! / k! * (n-1)! if(n == 0 && k == 0) return 1; ll ret = fac[n + k - 1]; (ret *= facInv[k]) %= MOD; (ret *= facInv[n - 1]) %= MOD; return ret; } ll nPk(ll n, ll k){//nPk = n! / (n-k)! if(k < 0 || k > n) return 0; ll ret = fac[n]; (ret *= facInv[n - k]) %= MOD; return ret; } private: void inverse(void){ inv[1] = 1; for (int i = 2; i <= MAX_N; ++i){ // inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD; inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD; } } void factroial(void){ fac[0] = facInv[0] = 1; for (int i = 1; i <= MAX_N; ++i){ fac[i] = (fac[i - 1] * i) % MOD; facInv[i] = (facInv[i - 1] * inv[i]) % MOD; } } }; int main(void){ cin >> R >> C >> X >> Y >> D >> L; MATH mt; ll ans = 0; for (int mask = 0; mask < (1<<4); ++mask){ int x = X, y = Y; if(mask & (1<<0)) x--; if(mask & (1<<1)) y--; if(mask & (1<<2)) x--; if(mask & (1<<3)) y--; if(x < 0 || y < 0) continue; if(x * y < D + L) continue; int cnt = 0; rep(i, 4) if(mask & (1<<i))cnt++; // printf("%d %d\n", x, y); if(cnt % 2){ // notans += mt.nCk(x * y, D + L) % MOD * fac[D + L] % MOD * facInv[D] % MOD * facInv[L] % MOD; ans -= mt.nCk(x * y, D) % MOD * mt.nCk(x * y - D, L) % MOD; }else{ // notans -= mt.nCk(x * y, D + L) % MOD * fac[D + L] % MOD * facInv[D] % MOD * facInv[L] % MOD; ans += mt.nCk(x * y, D) % MOD * mt.nCk(x * y - D, L) % MOD; } ans = (ans + MOD) % MOD; } ll time = ((R - X + 1) * (C - Y + 1)) % MOD; ans = ans * time % MOD; printf("%lld\n", ans % MOD); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder社の冬 |
User | mmxsrup |
Language | C++14 (GCC 5.4.1) |
Score | 101 |
Code Size | 2706 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | sub | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 100 / 100 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sub | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, test_03E.txt, test_04E.txt, test_07E.txt, test_08E.txt, test_11E.txt, test_12E.txt, test_15E.txt, test_16E.txt, test_19E.txt, test_20E.txt, test_23E.txt, test_24E.txt, test_27E.txt, test_28E.txt, test_31E.txt, test_32E.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_45E.txt, test_47E.txt |
All | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03E.txt, test_04E.txt, test_05.txt, test_06.txt, test_07E.txt, test_08E.txt, test_09.txt, test_10.txt, test_11E.txt, test_12E.txt, test_13.txt, test_14.txt, test_15E.txt, test_16E.txt, test_17.txt, test_18.txt, test_19E.txt, test_20E.txt, test_21.txt, test_22.txt, test_23E.txt, test_24E.txt, test_25.txt, test_26.txt, test_27E.txt, test_28E.txt, test_29.txt, test_30.txt, test_31E.txt, test_32E.txt, test_33.txt, test_34.txt, test_35.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45E.txt, test_46.txt, test_47E.txt, test_48.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01E.txt | AC | 1 ms | 256 KB |
00_sample_02E.txt | AC | 1 ms | 256 KB |
00_sample_03E.txt | AC | 1 ms | 256 KB |
00_sample_04.txt | AC | 1 ms | 256 KB |
test_01.txt | AC | 1 ms | 256 KB |
test_02.txt | AC | 1 ms | 256 KB |
test_03E.txt | AC | 1 ms | 256 KB |
test_04E.txt | AC | 1 ms | 256 KB |
test_05.txt | AC | 1 ms | 256 KB |
test_06.txt | AC | 1 ms | 256 KB |
test_07E.txt | AC | 1 ms | 256 KB |
test_08E.txt | AC | 1 ms | 256 KB |
test_09.txt | AC | 1 ms | 256 KB |
test_10.txt | AC | 1 ms | 256 KB |
test_11E.txt | AC | 1 ms | 256 KB |
test_12E.txt | AC | 1 ms | 256 KB |
test_13.txt | AC | 1 ms | 256 KB |
test_14.txt | AC | 1 ms | 256 KB |
test_15E.txt | AC | 1 ms | 256 KB |
test_16E.txt | AC | 1 ms | 256 KB |
test_17.txt | AC | 1 ms | 256 KB |
test_18.txt | AC | 1 ms | 256 KB |
test_19E.txt | AC | 1 ms | 256 KB |
test_20E.txt | AC | 1 ms | 256 KB |
test_21.txt | AC | 1 ms | 256 KB |
test_22.txt | AC | 1 ms | 256 KB |
test_23E.txt | AC | 1 ms | 256 KB |
test_24E.txt | AC | 1 ms | 256 KB |
test_25.txt | AC | 1 ms | 256 KB |
test_26.txt | AC | 1 ms | 256 KB |
test_27E.txt | AC | 1 ms | 256 KB |
test_28E.txt | AC | 1 ms | 256 KB |
test_29.txt | AC | 1 ms | 256 KB |
test_30.txt | AC | 1 ms | 256 KB |
test_31E.txt | AC | 1 ms | 256 KB |
test_32E.txt | AC | 1 ms | 256 KB |
test_33.txt | AC | 1 ms | 256 KB |
test_34.txt | AC | 1 ms | 256 KB |
test_35.txt | AC | 1 ms | 256 KB |
test_36E.txt | AC | 1 ms | 256 KB |
test_37E.txt | AC | 1 ms | 256 KB |
test_38E.txt | AC | 1 ms | 256 KB |
test_39E.txt | AC | 1 ms | 256 KB |
test_40.txt | AC | 1 ms | 256 KB |
test_41.txt | AC | 1 ms | 256 KB |
test_42.txt | AC | 1 ms | 256 KB |
test_43.txt | AC | 1 ms | 256 KB |
test_44.txt | AC | 1 ms | 256 KB |
test_45E.txt | AC | 1 ms | 256 KB |
test_46.txt | AC | 1 ms | 256 KB |
test_47E.txt | AC | 1 ms | 256 KB |
test_48.txt | AC | 1 ms | 256 KB |