제출 #521508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521508		cig32	Tents (JOI18_tents)	C++17	48 / 100	2096 ms	52908 KiB

tents

#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long

int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int f[MAXN];
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p & 1) return (((r * r) % MOD) * b) % MOD;
  return (r * r) % MOD;
}
int inv(int b) {
  return bm(b, MOD - 2);
}
int nCr(int n, int r) {
  int ans = f[n] * inv(f[r]);
  ans %= MOD;
  return (ans * inv(f[n-r])) % MOD;
}
void solve(int tc) {
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
  int H, W, ans = 0;
  cin >> H >> W;
  int cnt[H+1][W+1];
  for(int i=0; i<=W; i++) cnt[0][i] = 1;
  for(int i=0; i<=H; i++) cnt[i][0] = 1;
  cnt[1][1] = 5;
  for(int i=2; i<=H; i++) cnt[i][1] = 4*i + 1;
  for(int i=2; i<=W; i++) cnt[1][i] = 4*i + 1;
  for(int i=2; i<=H; i++) {
    for(int j=2; j<=W; j++) {
      cnt[i][j] = (cnt[i-1][j-1] * 5 + cnt[i-1][j-2] * 4 * (j-1) + cnt[i-2][j-1] * 4 * (i-1)) % MOD;
      cnt[i][j] += (i-1) * (j-1) * 16 * cnt[i-2][j-2];
      cnt[i][j] %= MOD;
    }
  }
  for(int x=0; x<=H; x++) {
    for(int y=0; x+2*y<=H && y+2*x<=W; y++) {
      int combs = nCr(H, x) * nCr(W, 2*x);
      combs %= MOD;
      combs *= f[2*x];
      combs %= MOD;
      combs *= inv(bm(2, x));
      combs %= MOD;
      combs *= nCr(W-2*x, y);
      combs %= MOD;
      combs *= nCr(H-x, 2*y);
      combs %= MOD;
      combs *= f[2*y];
      combs %= MOD;
      combs *= inv(bm(2, y));
      combs %= MOD;
      ans += combs * cnt[H - x - 2*y][W - y - 2*x];
      ans %= MOD;
    }
  }
  cout << (ans + MOD - 1) % MOD << "\n";
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

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