제출 #1192745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192745		nuutsnoynton	Zapina (COCI20_zapina)	C++20	110 / 110	127 ms	1780 KiB

zapina

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pll = pair < ll, ll > ;

const ll mod = 1e9 + 7;


ll dp[405][405]= {0};
ll fac[1002], inv_fac[1002], fac_inv[1002], inv[1002];

ll C(ll x, ll y) {
	return fac[x] * inv_fac[y] % mod * inv_fac[x - y] % mod;
}

 ll Pow(ll a, ll b) {
	if ( b == 0) return 1;
	if ( b == 1) return a % mod;
	ll r = Pow(a, b/2);
	r = r * r % mod;
	if ( b % 2 == 1) r = r * a % mod;
	return r;
}
ll invers(ll a) {
	if ( a == 0) return 1;
	return Pow(a, mod - 2);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, m, r, x, cur, y, i, lef, j, ans, t;
	
	cin >> n;
	
	
	fac[0] = fac[1] = inv_fac[0] = inv_fac[1] = inv[0] = inv[1] = 1;
	fac_inv[1] = 1;
	fac_inv[0] = 1;
	for (i = 2; i <= 1000; i ++) {
		fac[i] = fac[i- 1] * i % mod;
		inv[i] = (mod - mod/i) * inv[mod % i] % mod;
		inv_fac[i] = inv_fac[i - 1] * inv[i] % mod;
		fac_inv[i] = invers(fac[i]);
	}
	dp[0][n] = fac[n];
	
	for (i = 1; i <= n; i ++) {
		//cout << "\n";
		for ( lef = 0; lef <= n; lef ++) {
			for ( cur = 0; cur <= n; cur ++) {
				if ( cur == i) continue;
				if ( lef + cur > n) continue;
				dp[i][lef] = dp[i][lef] + (dp[i - 1][lef + cur] * fac_inv[cur] % mod );
				dp[i][lef] %= mod;
			//	cout << i << " " << lef << " " << dp[i][lef] << " "<<dp[i - 1][lef + cur] * invers(fac[cur]) % mod  << endl;
			} 
		}
//		for ( lef = 0; lef <= n; lef ++) {
//			cout << dp[i][lef] << " ";
//		}
//		cout << "\n";
	}
	ll s = Pow(n, n);
	s = s - dp[n][0];
	s %= mod;
	if ( s < 0) s += mod;
	
	cout << s << endl;
}

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