Submission #4026703
Source Code Expand
#include <iostream> #include <cassert> using namespace std; typedef long long ll; int R,C,X,Y,D,L; ll inf = 1e9+7; ll func[910] = {0}; ll inv[910] = {0}; ll mult(ll n, ll m){ if(m==1) return n%inf; else if(m%2==0){ ll t = mult(n,m/2); return (t*t)%inf; }else{ ll t = mult(n,m-1); return (t*n)%inf; } } void factorial(ll N){ for(ll i=0;i<=N;i++){ if(i==0){ func[i] = 1; inv[i] = 1; } else{ func[i] = (i*func[i-1])%inf; inv[i] = mult(func[i],inf-2); } } } ll comb(ll n,ll k){ if(n<k) return 0; if(k==0 || n==k) return 1; else return (((func[n]*inv[k])%inf)*inv[n-k])%inf; } int main(){ cin >> R >> C >> X >> Y >> D >> L; factorial(X*Y); ll ans = (comb(X*Y,D)*comb(X*Y-D,L))%inf,sub = 0; (sub += 2*(comb(X*(Y-1),D)*comb(X*(Y-1)-D,L))%inf + 2*(comb(Y*(X-1),D)*comb(Y*(X-1)-D,L))%inf)%=inf; sub -= (comb(X*(Y-2),D)*comb(X*(Y-2)-D,L))%inf + (comb(Y*(X-2),D)*comb(Y*(X-2)-D,L))%inf; (sub += 2*inf)%=inf; assert(sub>=0); sub -= 2*(comb((X-1)*(Y-1),D)*comb((X-1)*(Y-1)-D,L))%inf + 2*(comb((Y-1)*(X-1),D)*comb((Y-1)*(X-1)-D,L))%inf; (sub += 2*inf)%=inf; assert(sub>=0); (sub += 2*(comb((X-1)*(Y-2),D)*comb((X-1)*(Y-2)-D,L))%inf + 2*comb((Y-1)*(X-2),D)*comb((Y-1)*(X-2)-D,L))%=inf; if(X>=2 || Y>=2) sub -= (comb((X-2)*(Y-2),D)*comb((X-2)*(Y-2)-D,L))%inf; (sub += 2*inf)%=inf; assert(sub>=0); (ans += -sub+inf)%inf; cout << (ans*(R-X+1)*(C-Y+1))%inf << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder社の冬 |
User | idsigma |
Language | C++14 (GCC 5.4.1) |
Score | 101 |
Code Size | 1465 Byte |
Status | AC |
Exec Time | 2 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 | 2 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 | 2 ms | 256 KB |
test_05.txt | AC | 1 ms | 256 KB |
test_06.txt | AC | 2 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 | 2 ms | 256 KB |
test_11E.txt | AC | 1 ms | 256 KB |
test_12E.txt | AC | 2 ms | 256 KB |
test_13.txt | AC | 1 ms | 256 KB |
test_14.txt | AC | 2 ms | 256 KB |
test_15E.txt | AC | 2 ms | 256 KB |
test_16E.txt | AC | 2 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 | 2 ms | 256 KB |
test_23E.txt | AC | 1 ms | 256 KB |
test_24E.txt | AC | 2 ms | 256 KB |
test_25.txt | AC | 1 ms | 256 KB |
test_26.txt | AC | 1 ms | 256 KB |
test_27E.txt | AC | 2 ms | 256 KB |
test_28E.txt | AC | 2 ms | 256 KB |
test_29.txt | AC | 2 ms | 256 KB |
test_30.txt | AC | 2 ms | 256 KB |
test_31E.txt | AC | 1 ms | 256 KB |
test_32E.txt | AC | 2 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 |