oj.uz

Submission #521508

# Submission time Handle Problem Language Result Execution time Memory
521508 2022-02-02T09:44:28 Z cig32 Tents (JOI18_tents) C++17
48 / 100
 2000 ms 52908 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1880 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 6 ms 1996 KB Output is correct
7 Correct 6 ms 1996 KB Output is correct
8 Correct 4 ms 1996 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 12 ms 2124 KB Output is correct
11 Correct 2 ms 1880 KB Output is correct
12 Correct 33 ms 2520 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1880 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 6 ms 1996 KB Output is correct
7 Correct 6 ms 1996 KB Output is correct
8 Correct 4 ms 1996 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 12 ms 2124 KB Output is correct
11 Correct 2 ms 1880 KB Output is correct
12 Correct 33 ms 2520 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 2 ms 1880 KB Output is correct
15 Correct 1857 ms 45664 KB Output is correct
16 Correct 33 ms 4812 KB Output is correct
17 Correct 254 ms 11636 KB Output is correct
18 Correct 523 ms 13992 KB Output is correct
19 Execution timed out 2096 ms 52908 KB Time limit exceeded
20 Halted 0 ms 0 KB -