oj.uz

Submission #721799

# Submission time Handle Problem Language Result Execution time Memory
721799 2023-04-11T07:26:20 Z NothingXD Tents (JOI18_tents) C++14
100 / 100
 210 ms 35920 KB 
/*

   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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 35796 KB Output is correct
2 Correct 89 ms 35752 KB Output is correct
3 Correct 102 ms 35780 KB Output is correct
4 Correct 92 ms 35752 KB Output is correct
5 Correct 92 ms 35800 KB Output is correct
6 Correct 90 ms 35764 KB Output is correct
7 Correct 91 ms 35788 KB Output is correct
8 Correct 92 ms 35716 KB Output is correct
9 Correct 92 ms 35688 KB Output is correct
10 Correct 105 ms 35796 KB Output is correct
11 Correct 97 ms 35740 KB Output is correct
12 Correct 90 ms 35788 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 35796 KB Output is correct
2 Correct 89 ms 35752 KB Output is correct
3 Correct 102 ms 35780 KB Output is correct
4 Correct 92 ms 35752 KB Output is correct
5 Correct 92 ms 35800 KB Output is correct
6 Correct 90 ms 35764 KB Output is correct
7 Correct 91 ms 35788 KB Output is correct
8 Correct 92 ms 35716 KB Output is correct
9 Correct 92 ms 35688 KB Output is correct
10 Correct 105 ms 35796 KB Output is correct
11 Correct 97 ms 35740 KB Output is correct
12 Correct 90 ms 35788 KB Output is correct
13 Correct 90 ms 35784 KB Output is correct
14 Correct 89 ms 35784 KB Output is correct
15 Correct 135 ms 35808 KB Output is correct
16 Correct 91 ms 35764 KB Output is correct
17 Correct 105 ms 35780 KB Output is correct
18 Correct 104 ms 35912 KB Output is correct
19 Correct 151 ms 35724 KB Output is correct
20 Correct 139 ms 35920 KB Output is correct
21 Correct 119 ms 35676 KB Output is correct
22 Correct 141 ms 35728 KB Output is correct
23 Correct 102 ms 35772 KB Output is correct
24 Correct 179 ms 35780 KB Output is correct
25 Correct 159 ms 35820 KB Output is correct
26 Correct 172 ms 35836 KB Output is correct
27 Correct 210 ms 35796 KB Output is correct