Submission #535785

#	Time	Username	Problem	Language	Result	Execution time	Memory
535785		Soumya1	Tents (JOI18_tents)	C++17	100 / 100	136 ms	35676 KiB

tents

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
template<const int mod, const int modPhi>
struct Mint {
  int v;
  Mint() { v = 0; }
  Mint(int x) { v = x % mod; if (v < 0) v += mod; }
  Mint(long long x) { v = x % mod; if (v < 0) v += mod; }
  friend bool operator==(const Mint &a, const Mint &b) { return a.v == b.v; }
  friend bool operator!=(const Mint &a, const Mint &b) { return a.v != b.v; }
  friend bool operator<(const Mint &a, const Mint &b) { return a.v < b.v; }
  friend bool operator<=(const Mint &a, const Mint &b) { return a.v <= b.v; }
  friend bool operator>(const Mint &a, const Mint &b) { return a.v > b.v; }
  friend bool operator>=(const Mint &a, const Mint &b) { return a.v >= b.v; }
  Mint& operator+=(const Mint &a) { v += a.v; if (v >= mod) v -= mod; return *this; }
  Mint& operator-=(const Mint &a) { v -= a.v; if (v < 0) v += mod; return *this; }
  Mint& operator*=(const Mint &a) { v = (1LL * v * a.v) % mod; return *this; }
  Mint operator-() { return Mint(-v); }
  Mint& operator++() { return *this += 1; }
  Mint& operator--() { return *this -= 1; }
  friend Mint operator+(Mint a, const Mint b) { return a += b; }
  friend Mint operator-(Mint a, const Mint b) { return a -= b; }
  friend Mint operator*(Mint a, const Mint b) { return a *= b; }
  friend Mint min(Mint a, Mint b) { return (a < b ? b : a); }
  friend Mint max(Mint a, Mint b) { return (a > b ? a : b); }
  friend Mint power(Mint a, long long b) {
    Mint res = 1;
    while (b > 0) {
      if (b & 1) {
        res *= a;
      }
      a *= a, b >>= 1;
    }
    return res;
  }
  friend Mint inv(const Mint &a) { return power(a, modPhi - 1); }
  Mint operator/=(const Mint &a) { *this *= inv(a); return *this; }
  friend Mint operator/(Mint a, const Mint b) { return a /= b; }
  friend istream& operator>>(istream &in, Mint &a) { return in >> a.v; }
  friend ostream& operator<<(ostream &out, Mint a) { return out << a.v; }
};
const int mod = 1e9 + 7;
using mint = Mint<mod, mod - 1>;
void testCase() {
  int w, h;
  cin >> w >> h;
  vector<vector<mint>> dp(w + 1, vector<mint> (h + 1, mint(1)));
  for (int i = 1; i <= w; i++) {
    for (int j = 1; j <= h; j++) {
      dp[i][j] = mint(4 * j) * dp[i - 1][j - 1];
      dp[i][j] += dp[i - 1][j];
      if (j >= 2) dp[i][j] += mint(j * (j - 1) / 2) * dp[i - 1][j - 2];
      if (i >= 2) dp[i][j] += mint((i - 1) * j) * dp[i - 2][j - 1];
    }
  }
  cout << dp[w][h] - 1 << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52