제출 #856193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856193		serifefedartar	Zapina (COCI20_zapina)	C++17	110 / 110	226 ms	2644 KiB

zapina

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 400;

ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

ll dp[MAXN][MAXN][2];
ll fact[5 * MAXN], inv[5 * MAXN];
ll nCr(ll n, ll r) {
	return ((fact[n] * inv[r]) % MOD * inv[n-r]) % MOD;
}

int main() {
	fast
	fact[0] = inv[0] = 1;
	for (ll i = 1; i < 5*MAXN; i++) {
		fact[i] = (fact[i-1] * i) % MOD;
		inv[i] = expo(fact[i], MOD - 2);
	}

	int N;
	cin >> N;

	dp[0][0][0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int last = 0; last <= N; last++) {
			for (int now = last; now <= N; now++) {
				int rem = N - last;
				ll choose = nCr(rem, now - last);

				if (now - last != i)
					dp[i][now][0] = (dp[i][now][0] + (dp[i-1][last][0] * choose) % MOD) % MOD;

				if (i == now - last)
					dp[i][now][1] = (dp[i][now][1] + ((dp[i-1][last][0] + dp[i-1][last][1]) * choose) % MOD) % MOD;
				else
					dp[i][now][1] = (dp[i][now][1] + (dp[i-1][last][1] * choose) % MOD) % MOD;
			}
		}
	}
	cout << dp[N][N][1] << "\n";
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55