제출 #201804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201804		EntityIT	Tents (JOI18_tents)	C++14	100 / 100	129 ms	35832 KiB

tents

#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;
}

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