oj.uz

답안 #401310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401310 2021-05-09T19:58:09 Z arwaeystoamneg Tents (JOI18_tents) C++17
100 / 100
 1794 ms 35760 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint() { v = 0; }
	mint(ll _v) {
		v = int((-MOD < _v&& _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mint& a, const mint& b) {
		return a.v == b.v;
	}
	friend bool operator!=(const mint& a, const mint& b) {
		return !(a == b);
	}
	friend bool operator<(const mint& a, const mint& b) {
		return a.v < b.v;
	}

	mint& operator+=(const mint& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this;
	}
	mint& operator-=(const mint& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this;
	}
	mint& operator*=(const mint& m) {
		v = int((ll)v * m.v % MOD); return *this;
	}
	mint& operator/=(const mint& m) { return (*this) *= inv(m); }
	friend mint power(mint a, ll p) {// MAKE SURE YOU ARE USING THE CORRECT VERSION OF POW!!!!!!!!
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	friend mint inv(const mint& a) {
		assert(a.v != 0);
		return power(a, MOD - 2);
	}

	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

typedef mint<inf, 5> mi; // 5 is primitive root for both common mods
const int MAX = 3005;//3005;
mi dp[MAX][MAX];
int main()
{
	setIO("");
	int n, m;
	cin >> n >> m;
	FOR(i, 1, MAX)dp[1][i] = dp[i][1] = 4 * i + (i * (i - 1)) / 2;
	FOR(i, 2, MAX)
	{
		FOR(j, 2, MAX)
		{
			/*
			mi ans = dp[i - 1][j - 1];


			ans += 4 * (dp[i - 1][j - 1] + 1);
			ans += (j - 1) * (1 + dp[i - 1][j - 2]);
			ans += (i - 1) * (1 + dp[i - 2][j - 1]);

			// only y
			ans += 4 * (j - 1) * (1 + dp[i - 1][j - 2]);
			ans += (i - 1) * (j - 1) * (1 + dp[i - 2][j - 2]);
			
			// only x
			ans += 4 * (i - 1) * (1 + dp[i - 2][j - 1]);
			ans += (i - 1) * (j - 1) * (1 + dp[i - 2][j - 2]);

			// both
			ans += 16 * (i - 1) * (j - 1) * (1 + dp[i - 2][j - 2]);
			if (i >= 3)
				ans += 4 * (i - 1) * (j - 1) * (i - 2) * (1 + dp[i - 3][j - 2]);
			if (j >= 3)
				ans += 4 * (i - 1) * (j - 1) * (j - 2) * (1 + dp[i - 2][j - 3]);
			if (i >= 3 && j >= 3)
				ans += (i - 1) * (j - 1) * (i - 2) * (j - 2) * (1 + dp[i - 3][j - 3]);


			dp[i][j] = ans;
			*/
			mi ans = dp[i][j - 1];
			ans += 4 * i * (dp[i - 1][j - 1] + 1);
			ans += i * (j - 1) * (dp[i - 1][j - 2] + 1);
			ans += i * (i - 1) * (dp[i - 2][j - 1] + 1) * inv((mi)2);
			dp[i][j] = ans;
		}
	}
	cout << (int)dp[n][m] << endl;
}

Subtask #1
48.0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1777 ms 35660 KB Output is correct
2 Correct 1780 ms 35652 KB Output is correct
3 Correct 1774 ms 35640 KB Output is correct
4 Correct 1794 ms 35660 KB Output is correct
5 Correct 1784 ms 35656 KB Output is correct
6 Correct 1771 ms 35760 KB Output is correct
7 Correct 1774 ms 35660 KB Output is correct
8 Correct 1769 ms 35644 KB Output is correct
9 Correct 1765 ms 35660 KB Output is correct
10 Correct 1781 ms 35652 KB Output is correct
11 Correct 1772 ms 35732 KB Output is correct
12 Correct 1775 ms 35640 KB Output is correct

Subtask #2
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1777 ms 35660 KB Output is correct
2 Correct 1780 ms 35652 KB Output is correct
3 Correct 1774 ms 35640 KB Output is correct
4 Correct 1794 ms 35660 KB Output is correct
5 Correct 1784 ms 35656 KB Output is correct
6 Correct 1771 ms 35760 KB Output is correct
7 Correct 1774 ms 35660 KB Output is correct
8 Correct 1769 ms 35644 KB Output is correct
9 Correct 1765 ms 35660 KB Output is correct
10 Correct 1781 ms 35652 KB Output is correct
11 Correct 1772 ms 35732 KB Output is correct
12 Correct 1775 ms 35640 KB Output is correct
13 Correct 1777 ms 35644 KB Output is correct
14 Correct 1762 ms 35640 KB Output is correct
15 Correct 1763 ms 35660 KB Output is correct
16 Correct 1764 ms 35644 KB Output is correct
17 Correct 1773 ms 35660 KB Output is correct
18 Correct 1765 ms 35660 KB Output is correct
19 Correct 1775 ms 35640 KB Output is correct
20 Correct 1769 ms 35644 KB Output is correct
21 Correct 1761 ms 35660 KB Output is correct
22 Correct 1783 ms 35640 KB Output is correct
23 Correct 1778 ms 35660 KB Output is correct
24 Correct 1777 ms 35640 KB Output is correct
25 Correct 1775 ms 35660 KB Output is correct
26 Correct 1773 ms 35532 KB Output is correct
27 Correct 1765 ms 35656 KB Output is correct