Submission #2117421


Source Code Expand

#include <cassert>
#include <iomanip>
#include <iostream>

using namespace std;

template<int mod>
class Modulo {
  public:
    constexpr Modulo(): num(0) {}
    constexpr Modulo(int n): num(n % mod) {}
    constexpr Modulo(Modulo const &) = default;
    constexpr int data() const { return num; }
    constexpr Modulo &operator+=(Modulo other) {
      num = (num + other.num) % mod;
      return *this;
    }
    constexpr Modulo &operator-=(Modulo other) {
      num = (num + mod - other.num) % mod;
      return *this;
    }
    constexpr Modulo &operator*=(Modulo other) {
      long long n = ((long long)num) * ((long long)other.num);
      num = n % mod;
      return *this;
    }
    constexpr Modulo &operator/=(Modulo other) {
      *this *= other.inverse();
      return *this;
    }
    constexpr static Modulo pow(Modulo a, int n, Modulo res) {
      if (n == 0) { return res; }
      return pow(a*a, n/2, (n&1)?(res*a):res);
    }
    constexpr Modulo inverse() const {
      return pow(*this, mod-2, Modulo(1));
    }
  private:
    int num;
};

template<int mod>
constexpr Modulo<mod> operator+(Modulo<mod> a, Modulo<mod> b) {
  a += b;
  return a;
}

template<int mod>
constexpr Modulo<mod> operator-(Modulo<mod> a, Modulo<mod> b) {
  a -= b;
  return a;
}

template<int mod>
constexpr Modulo<mod> operator*(Modulo<mod> a, Modulo<mod> b) {
  a *= b;
  return a;
}

template<int mod>
constexpr Modulo<mod> pow(Modulo<mod> a, int n) {
  return Modulo<mod>::pow(a, n, 1);
}

template<int mod>
constexpr Modulo<mod> operator/(Modulo<mod> a, Modulo<mod> b) {
  a /= b;
  return a;
}

template<int mod, int size>
struct Factorial {
  using Mod = Modulo<mod>;
  Mod fact[size];
  constexpr Factorial(): fact() {
    fact[0] = 1;
    for (int i = 1; i < size; ++i) {
      fact[i] = Mod(i) * fact[i-1];
    }
  }
  Mod comb(int n, int k) const {
    assert(k <= n && n < size);
    return fact[n] / (fact[k]*fact[n-k]);
  }
};

constexpr int mod = 1e9 + 7;
constexpr int FMAX = 1000;
using Mod = Modulo<mod>;
constexpr auto fact = Factorial<mod, FMAX>();

Mod cases(int x, int y, int d, int l) {
  if (d+l > x*y || x <= 0 || y <= 0) { return 0; }
  int const o = x*y - d - l;
  return fact.fact[x*y] / (fact.fact[d]*fact.fact[l]*fact.fact[o]);
}

Mod solve(int r, int c, int x, int y, int d, int l) {
  Mod ans = cases(x, y, d, l);
  ans -= (cases(x-1,y,d,l)+cases(x,y-1,d,l)) * Mod(2);
  ans += Mod(4)*cases(x-1,y-1,d,l) + cases(x,y-2,d,l) + cases(x-2,y,d,l);
  ans -= (cases(x-2,y-1,d,l)+cases(x-1,y-2,d,l)) * Mod(2);
  ans += cases(x-2,y-2,d,l);
  ans *= Mod(r+1-x);
  ans *= Mod(c+1-y);
  return ans;
}

int main() {
  int R, C, X, Y, D, L;
  cin >> R >> C >> X >> Y >> D >> L;
  cout << solve(R, C, X, Y, D, L).data() << endl;
  return 0;
}

Submission Info

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

Judge Result

Set Name sub All
Score / Max Score 100 / 100 1 / 1
Status
AC × 25
AC × 52
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