제출 #201804

#제출 시각아이디문제언어결과실행 시간메모리
201804EntityITTents (JOI18_tents)C++14
100 / 100
129 ms35832 KiB
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int mod = 1e9 + 7;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

struct Mint {
  int a;
  Mint(int _a = 0) : a(_a) {}
  friend ostream& operator << (ostream &out, const Mint &_) {
    out << _.a;
    return out;
  }

  bool operator == (const Mint &_) const { return a == _.a; }
  bool operator ! () const { return !a; }

  Mint operator + (const Mint &_) const {
    int ret = a + _.a;
    return ret < mod ? Mint(ret) : Mint(ret - mod);
  }
  Mint operator - (const Mint &_) const { return *this + Mint(mod - _.a); }
  Mint operator * (const Mint &_) const { return Mint( (int)( (LL)a * _.a % mod) ); }
  friend Mint& operator += (Mint &a, const Mint &b) { return a = a + b; }
  friend Mint& operator -= (Mint &a, const Mint &b) { return a = a - b; }
  friend Mint& operator *= (Mint &a, const Mint &b) { return a = a * b; }
  Mint& operator ++ () { return *this = *this + Mint(1); }
  Mint& operator -- () { return *this = *this - Mint(1); }

  template<class T> Mint binPow(T exp) const {
    Mint ret(1), c = *this;
    for (; exp; exp >>= 1, c *= c) if (exp & 1) ret *= c;
    return ret;
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, m; cin >> n >> m;

  vector<vector<Mint> > f(n + 1, vector<Mint>(m + 1) );
  for (int i = 0; i < n; ++i) f[i][0] = Mint(1);
  for (int j = 0; j < m; ++j) f[0][j] = Mint(1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      f[i][j] += f[i - 1][j];
      f[i][j] += f[i - 1][j - 1] * Mint(4 * j);
      if (j > 1) f[i][j] += f[i - 1][j - 2] * Mint(j * (j - 1) / 2);
      if (i > 1) f[i][j] += f[i - 2][j - 1] * Mint(j * (i - 1) );
    }
  }

  cout << f[n][m] << '\n';

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...