제출 #721799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721799		NothingXD	Tents (JOI18_tents)	C++14	100 / 100	210 ms	35920 KiB

tents

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
  */
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e3 + 10;
const int mod = 1e9 + 7;

int add(int x, int y){
	int res = x + y;
	if (res >= mod) return res - mod;
	if (res < 0) return res + mod;
	return res;
}

int pwr(int a, int b){
	int res = 1;
	for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res;
}

int n, m, dp[maxn][maxn], fact[maxn], invfact[maxn], invpw[maxn];

int C(int n, int k){
	if (k < 0 || k > n) return 0;
	return 1ll * fact[n] * invfact[k] % mod * invfact[n-k] % mod;
}

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

	fact[0] = invfact[0] = invpw[0] = 1;
	invpw[1] = pwr(2, mod-2);
	for (int i = 1; i < maxn; i++){
		fact[i] = 1ll * fact[i-1] * i % mod;
		invpw[i] = 1ll * invpw[i-1] * invpw[1] % mod;
		invfact[i] = pwr(fact[i], mod-2);
	}

	for (int i = 0; i < maxn; i++){
		dp[0][i] = 1;
	}
	for (int i = 1; i < maxn; i++){
		dp[i][0] = 1;
		for (int j = 1; j < maxn; j++){
			dp[i][j] = add(dp[i-1][j], 4ll * dp[i-1][j-1] * j % mod);
		}
	}

	cin >> n >> m;

	int ans = 0;

	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= m; j++){
			if (2 * i + j > m || 2 * j + i > n) continue;
			int res = 1ll * fact[n] * invfact[i] % mod * invpw[j] % mod * invfact[n-2*j-i] % mod;
			res = 1ll * res * fact[m] % mod * invfact[j] % mod * invpw[i] % mod * invfact[m-2*i-j] % mod;
			res = 1ll * res * dp[n-2*j-i][m-2*i-j] % mod;
			ans = add(ans, res);
		}
	}
	
	cout << add(ans, -1) << '\n';

	return 0;
}

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