oj.uz

Submission #97740

# Submission time Handle Problem Language Result Execution time Memory
97740 2019-02-17T23:01:33 Z Anai Tents (JOI18_tents) C++14
100 / 100
 178 ms 71288 KB 
#include <bits/stdc++.h>
using namespace std;

template<long long MOD>
class Num {
private:
	long long expow(long long base, long long e) const {
		long long ans = 1;
		for (; e > 0; e/= 2) {
			if (e % 2)
				ans = ans * base % MOD;
			base = base * base % MOD; }
		return ans; }

public:
	long long val;

	Num(long long _val) {
		val = _val % MOD;
		val = val < 0 ? val + MOD : val; }
	Num() : val(0) { }

	inline Num operator + (const Num &arg) const {
		Num res;
		res.val = val + arg.val;
		res.val = res.val >= MOD ? res.val - MOD : res.val;
		return res; }

	inline Num operator - (const Num &arg) const {
		Num res;
		res.val = val - arg.val;
		res.val = res.val < 0 ? res.val + MOD : res.val;
		return res; }

	inline Num operator - () const {
		Num res;
		res.val = MOD - res.val;
		res.val = res.val == MOD ? 0 : res.val;
		return res; }

	inline Num operator ^ (const int &arg) const {
		return Num(expow(val, arg)); }

	inline Num operator * (const Num &arg) const {
		return Num(val * arg.val); }

	inline Num operator / (const Num &arg) const {
		return Num(val * expow(arg.val, MOD - 2)); }

	inline void operator += (const Num &arg) {
		(*this) = (*this) + arg; }

	inline void operator -= (const Num &arg) {
		(*this) = (*this) - arg; }

	inline void operator *= (const Num &arg) {
		(*this) = (*this) * arg; }

	inline void operator /= (const Num &arg) {
		(*this) = (*this) / arg; }

	inline void operator ^= (const long long &arg) {
		val = expow(val, arg); } };

template<long long MOD>
ostream &operator << (ostream &fo, const Num<MOD> &c) {
	fo << c.val;
	return fo; }

template<long long MOD>
istream &operator >> (istream &fi, Num<MOD> &c) {
	fi >> c.val;
	c = Num<MOD>(c.val);
	return fi; }

const int N = 3005, MOD = 1e9 + 7;


Num<MOD> dp[N][N];
int n, m;

int main() {
#ifdef HOME
	freopen("joi_tents.in", "r", stdin);
	freopen("joi_tents.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Num<MOD> ant;

	cin >> n >> m;

	for (int i = 0; i < N; ++i)
		dp[0][i] = dp[i][0] = 1;

	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j) {
		dp[i][j]+= dp[i - 1][j];
		if (j >= 2)
			dp[i][j]+= dp[i - 1][j - 2] * (j * (j - 1) / 2);
		if (i >= 2)
			dp[i][j]+= dp[i - 2][j - 1] * (i - 1) * j;
		dp[i][j]+= dp[i - 1][j - 1] * j * 4; }


	cout << dp[n][m] - 1 << endl;

	return 0; }

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 71288 KB Output is correct
2 Correct 56 ms 71160 KB Output is correct
3 Correct 56 ms 71032 KB Output is correct
4 Correct 54 ms 71160 KB Output is correct
5 Correct 56 ms 71032 KB Output is correct
6 Correct 56 ms 70956 KB Output is correct
7 Correct 54 ms 71132 KB Output is correct
8 Correct 53 ms 71060 KB Output is correct
9 Correct 58 ms 71032 KB Output is correct
10 Correct 56 ms 71032 KB Output is correct
11 Correct 56 ms 71032 KB Output is correct
12 Correct 59 ms 71032 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 71288 KB Output is correct
2 Correct 56 ms 71160 KB Output is correct
3 Correct 56 ms 71032 KB Output is correct
4 Correct 54 ms 71160 KB Output is correct
5 Correct 56 ms 71032 KB Output is correct
6 Correct 56 ms 70956 KB Output is correct
7 Correct 54 ms 71132 KB Output is correct
8 Correct 53 ms 71060 KB Output is correct
9 Correct 58 ms 71032 KB Output is correct
10 Correct 56 ms 71032 KB Output is correct
11 Correct 56 ms 71032 KB Output is correct
12 Correct 59 ms 71032 KB Output is correct
13 Correct 60 ms 71004 KB Output is correct
14 Correct 55 ms 71028 KB Output is correct
15 Correct 160 ms 71032 KB Output is correct
16 Correct 65 ms 71032 KB Output is correct
17 Correct 72 ms 71032 KB Output is correct
18 Correct 87 ms 71124 KB Output is correct
19 Correct 139 ms 71032 KB Output is correct
20 Correct 127 ms 71136 KB Output is correct
21 Correct 99 ms 71036 KB Output is correct
22 Correct 98 ms 71036 KB Output is correct
23 Correct 86 ms 71184 KB Output is correct
24 Correct 178 ms 71072 KB Output is correct
25 Correct 150 ms 71100 KB Output is correct
26 Correct 154 ms 71160 KB Output is correct
27 Correct 165 ms 71032 KB Output is correct