Submission #3010316

Source Code Expand

Copy
#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define MAX 1005
using namespace std;

long long factorial[MAX] = {0}, finverse[MAX] = {0},
          inverse[MAX] = {0};

void smodfact() {
  factorial[0] = factorial[1] = 1;
  finverse[0] = finverse[1] = 1;
  inverse[1] = 1;
  for(int i = 2; i < MAX; ++i) {
    factorial[i] = factorial[i - 1] * i % N;
    inverse[i] = N - (inverse[N % i] * (N / i)) % N;
    finverse[i] = finverse[i - 1] * inverse[i] % N;
  }
}

long long calccomb(long long n, long long k) {
  if(n < 0 || k < 0 || n < k) return 0;
  return factorial[n] * finverse[k] % N * finverse[n - k] %
         N;
}
long long r, c, x, y, d, l, now = 1, nextn = 0;
long long ans = 0;

int main() {
  smodfact();
  cin >> r >> c >> x >> y >> d >> l;
  ans = (r - x + 1) * (c - y + 1) % N;
  // 0辺
  now = calccomb(x * y, (x * y) - l - d) *
        calccomb(l + d, d) % N;
  // 1辺
  nextn = 2 * calccomb((x - 1) * y, (x - 1) * y - l - d) %
          N * calccomb(l + d, d) % N;
  nextn += 2 * calccomb((y - 1) * x, x * (y - 1) - l - d) %
           N * calccomb(l + d, d) % N;
  nextn %= N;
  now -= nextn;
  now %= N;
  // 2辺
  nextn = 4 *
          calccomb((x - 1) * (y - 1),
                   (x - 1) * (y - 1) - l - d) %
          N * calccomb(l + d, d) % N;
  nextn += calccomb((x - 2) * y, (x - 2) * y - l - d) *
           calccomb(l + d, d) % N;
  nextn %= N;
  nextn += calccomb(x * (y - 2), x * (y - 2) - l - d) *
           calccomb(l + d, d) % N;
  nextn %= N;
  now += nextn;
  now %= N;
  // 3辺
  nextn = 2 *
          calccomb((x - 2) * (y - 1),
                   (x - 2) * (y - 1) - l - d) %
          N * calccomb(l + d, d) % N;
  nextn += 2 *
           calccomb((x - 1) * (y - 2),
                    (x - 1) * (y - 2) - l - d) %
           N * calccomb(l + d, d) % N;
  nextn %= N;
  now -= nextn;
  now %= N;
  //一周
  if((x - 2) >= 0 && (y - 2) >= 0)
    nextn = calccomb((x - 2) * (y - 2),
                     (x - 2) * (y - 2) - l - d) %
            N * calccomb(l + d, d) % N;
  now += nextn;
  now %= N;
  if(now < 0) now += N;

  ans *= now;
  ans %= N;
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task D - AtCoder社の冬
User m_tsubasa
Language C++14 (GCC 5.4.1)
Score 101
Code Size 2229 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
sub 100 / 100 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 1 / 1 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 1 ms 256 KB
00_sample_02E.txt 1 ms 256 KB
00_sample_03E.txt 1 ms 256 KB
00_sample_04.txt 1 ms 256 KB
test_01.txt 1 ms 256 KB
test_02.txt 1 ms 256 KB
test_03E.txt 1 ms 256 KB
test_04E.txt 1 ms 256 KB
test_05.txt 1 ms 256 KB
test_06.txt 1 ms 256 KB
test_07E.txt 1 ms 256 KB
test_08E.txt 1 ms 256 KB
test_09.txt 1 ms 256 KB
test_10.txt 1 ms 256 KB
test_11E.txt 1 ms 256 KB
test_12E.txt 1 ms 256 KB
test_13.txt 1 ms 256 KB
test_14.txt 1 ms 256 KB
test_15E.txt 1 ms 256 KB
test_16E.txt 1 ms 256 KB
test_17.txt 1 ms 256 KB
test_18.txt 1 ms 256 KB
test_19E.txt 1 ms 256 KB
test_20E.txt 1 ms 256 KB
test_21.txt 1 ms 256 KB
test_22.txt 1 ms 256 KB
test_23E.txt 1 ms 256 KB
test_24E.txt 1 ms 256 KB
test_25.txt 1 ms 256 KB
test_26.txt 1 ms 256 KB
test_27E.txt 1 ms 256 KB
test_28E.txt 1 ms 256 KB
test_29.txt 1 ms 256 KB
test_30.txt 1 ms 256 KB
test_31E.txt 1 ms 256 KB
test_32E.txt 1 ms 256 KB
test_33.txt 1 ms 256 KB
test_34.txt 1 ms 256 KB
test_35.txt 1 ms 256 KB
test_36E.txt 1 ms 256 KB
test_37E.txt 1 ms 256 KB
test_38E.txt 1 ms 256 KB
test_39E.txt 1 ms 256 KB
test_40.txt 1 ms 256 KB
test_41.txt 1 ms 256 KB
test_42.txt 1 ms 256 KB
test_43.txt 1 ms 256 KB
test_44.txt 1 ms 256 KB
test_45E.txt 1 ms 256 KB
test_46.txt 1 ms 256 KB
test_47E.txt 1 ms 256 KB
test_48.txt 1 ms 256 KB