Submission #6902881
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
int mod = 1'000'000'007;
long long modpow(long long x, long long y){
if (y == 0) return 1;
if (y % 2) return x * modpow(x, y - 1) % mod;
return modpow(x, y / 2) * modpow(x, y / 2) % mod;
}
long long cmb(long long x, long long y){
long long acc = 1;
long long div = 1;
for (int i = 0; i < y; i++){
acc *= x - i;
acc %= mod;
div *= i + 1;
div %= mod;
}
return acc * modpow(div, mod - 2) % mod;
}
int main(){
int r, c, x, y, d, l;
cin >> r >> c >> x >> y >> d >> l;
long long ans = 0;
if (x == 1 && y == 1){
ans = 1;
}
else if (x == 1 || y == 1){
vector<int> dd = {0, 1, 1, 2};
vector<int> dl = {2, 1, 1, 0};
for (int i = 0; i < 4; i++){
if (dd[i] > d || dl[i] > l) continue;
long long tmp = 1;
tmp *= cmb(x * y - dd[i] - dl[i], d - dd[i]);
tmp %= mod;
tmp *= cmb(x * y - d - dl[i], l - dl[i]);
tmp %= mod;
ans += tmp;
ans %= mod;
}
}
else {
vector<int> dd = {0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 2, 1, 1, 1, 0, 3, 2, 2, 2, 1, 1, 1, 0, 3, 2, 2, 2, 1, 1, 1, 0, 3, 2, 2, 2, 1, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 0, 2, 1, 1, 0};
vector<int> dl = {4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 1, 1, 1, 2, 2, 2, 3, 0, 1, 1, 1, 2, 2, 2, 3, 0, 1, 1, 1, 2, 2, 2, 3, 0, 1, 1, 1, 2, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2};
for (int i = 0; i < 72; i++){
if (dd[i] > d || dl[i] > l || x * y - 4 + dd[i] + dl[i] < d + l) continue;
long long tmp = 1;
tmp *= cmb(x * y - 4, d - dd[i]);
tmp %= mod;
tmp *= cmb(x * y - 4 - d + dd[i], l - dl[i]);
tmp %= mod;
ans += tmp;
ans %= mod;
}
}
ans *= r - x + 1;
ans %= mod;
ans *= c - y + 1;
ans %= mod;
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
D - AtCoder社の冬 |
User |
lemon_ |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2147 Byte |
Status |
WA |
Exec Time |
2 ms |
Memory |
384 KB |
Judge Result
Set Name |
sub |
All |
Score / Max Score |
100 / 100 |
0 / 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 |
WA |
2 ms |
256 KB |
test_01.txt |
WA |
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 |
WA |
1 ms |
256 KB |
test_07E.txt |
AC |
1 ms |
256 KB |
test_08E.txt |
AC |
1 ms |
256 KB |
test_09.txt |
WA |
1 ms |
256 KB |
test_10.txt |
WA |
1 ms |
256 KB |
test_11E.txt |
AC |
1 ms |
256 KB |
test_12E.txt |
AC |
1 ms |
256 KB |
test_13.txt |
WA |
1 ms |
256 KB |
test_14.txt |
WA |
1 ms |
256 KB |
test_15E.txt |
AC |
1 ms |
256 KB |
test_16E.txt |
AC |
1 ms |
256 KB |
test_17.txt |
WA |
1 ms |
256 KB |
test_18.txt |
WA |
1 ms |
256 KB |
test_19E.txt |
AC |
1 ms |
256 KB |
test_20E.txt |
AC |
1 ms |
256 KB |
test_21.txt |
WA |
1 ms |
256 KB |
test_22.txt |
WA |
1 ms |
256 KB |
test_23E.txt |
AC |
1 ms |
256 KB |
test_24E.txt |
AC |
1 ms |
256 KB |
test_25.txt |
WA |
2 ms |
384 KB |
test_26.txt |
WA |
1 ms |
256 KB |
test_27E.txt |
AC |
1 ms |
256 KB |
test_28E.txt |
AC |
1 ms |
256 KB |
test_29.txt |
WA |
1 ms |
256 KB |
test_30.txt |
WA |
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 |
WA |
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 |
WA |
1 ms |
256 KB |
test_41.txt |
AC |
1 ms |
256 KB |
test_42.txt |
WA |
1 ms |
256 KB |
test_43.txt |
AC |
1 ms |
256 KB |
test_44.txt |
WA |
1 ms |
256 KB |
test_45E.txt |
AC |
1 ms |
256 KB |
test_46.txt |
WA |
1 ms |
256 KB |
test_47E.txt |
AC |
2 ms |
256 KB |
test_48.txt |
AC |
1 ms |
256 KB |