| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047073 |
2024-08-07T08:35:21 Z |
정민찬(#11024) |
Ruins 3 (JOI20_ruins3) |
C++17 |
|
6000 ms |
22868 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll mod = 1e9 + 7;
ll fastpow(ll a, ll b) {
ll ret = 1;
while (b) {
if (b % 2 == 1) ret = ret * a % mod;
b /= 2;
a = a * a % mod;
}
return ret;
}
ll dp[2][610][1210];
ll br[1210][1210];
ll com[1210];
ll fac[1210], inv[1210];
ll P(ll n, ll r) {
if (n < r) return 0;
return fac[n] * inv[n-r] % mod;
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
com[0] = 1;
com[1] = 2;
br[1][1] = 1;
br[1][2] = 1;
for (ll i=2; i<=1200; i++) {
ll sum = 0;
for (ll j=i-1; j<=i*2-1; j++) {
sum = (sum + br[i-1][j]) % mod;
br[i][j+1] = sum;
com[i] = (com[i] + sum) % mod;
}
}
fac[0] = 1;
for (ll i=1; i<=1200; i++) {
fac[i] = fac[i-1] * i % mod;
}
inv[1200] = fastpow(fac[1200], mod-2);
for (ll i=1200-1; i>=0; i--) {
inv[i] = inv[i+1] * (i+1) % mod;
}
ll N;
cin >> N;
vector<ll> a(N);
vector<ll> chk(2*N, 0);
for (ll i=0; i<N; i++) {
cin >> a[i];
a[i] --;
chk[a[i]] = 1;
}
dp[0][0][0] = 1;
for (ll i=2*N-1; i>=0; i--) {
ll cnt = 2*N - i;
for (ll j=0; j<=cnt; j++) {
for (ll k=j; k<=j*2; k++) {
dp[i&1][j][k] = 0;
}
}
if (!chk[i]) {
for (ll j=0; j<=cnt-1; j++) {
for (ll k=j; k<2*j; k++) {
dp[i&1][j][k+1] += dp[i&1^1][j][k] * (2*j - k) % mod;
dp[i&1][j][k+1] %= mod;
}
}
}
else {
for (ll j=0; j<=cnt-1; j++) {
for (ll k=j; k<=min(cnt-1, 2*j); k++) {
if (cnt - k > N-j) continue;
if (cnt - k == N-j) {
dp[i&1][N][cnt] += dp[i&1^1][j][k] * fac[N-j-1] % mod
* com[N-j-1] % mod * (N-j+1) % mod;
dp[i&1][N][cnt] %= mod;
}
else {
dp[i&1][j][k] += dp[i&1^1][j][k];
dp[i&1][j][k] %= mod;
for (ll l=1; l<=cnt-k; l++) {
dp[i&1][j+l][k+l] += dp[i&1^1][j][k] * P(cnt-k-1, l-1) % mod
* com[l-1] % mod * (l+1) % mod;
dp[i&1][j+l][k+l] %= mod;
}
}
}
}
}
}
ll ans = dp[0][N][2*N];
ll inv2 = fastpow(2, mod-2);
for (ll i=0; i<N; i++) {
ans = ans * inv2 % mod;
}
cout << ans << '\n';
}
Compilation message
ruins3.cpp: In function 'int main()':
ruins3.cpp:72:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
72 | dp[i&1][j][k+1] += dp[i&1^1][j][k] * (2*j - k) % mod;
| ~^~
ruins3.cpp:82:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
82 | dp[i&1][N][cnt] += dp[i&1^1][j][k] * fac[N-j-1] % mod
| ~^~
ruins3.cpp:87:46: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
87 | dp[i&1][j][k] += dp[i&1^1][j][k];
| ~^~
ruins3.cpp:90:54: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
90 | dp[i&1][j+l][k+l] += dp[i&1^1][j][k] * P(cnt-k-1, l-1) % mod
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 6 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
4 ms |
14892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 10 |
Correct |
4 ms |
14684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 6 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
4 ms |
14892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 10 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 11 |
Correct |
7 ms |
16732 KB |
Output is correct |
| 12 |
Correct |
6 ms |
16732 KB |
Output is correct |
| 13 |
Correct |
7 ms |
16960 KB |
Output is correct |
| 14 |
Correct |
7 ms |
16728 KB |
Output is correct |
| 15 |
Correct |
6 ms |
16732 KB |
Output is correct |
| 16 |
Correct |
8 ms |
16940 KB |
Output is correct |
| 17 |
Correct |
6 ms |
16732 KB |
Output is correct |
| 18 |
Correct |
7 ms |
16732 KB |
Output is correct |
| 19 |
Correct |
7 ms |
16784 KB |
Output is correct |
| 20 |
Correct |
7 ms |
16960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 6 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
4 ms |
14892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 10 |
Correct |
4 ms |
14684 KB |
Output is correct |
| 11 |
Correct |
7 ms |
16732 KB |
Output is correct |
| 12 |
Correct |
6 ms |
16732 KB |
Output is correct |
| 13 |
Correct |
7 ms |
16960 KB |
Output is correct |
| 14 |
Correct |
7 ms |
16728 KB |
Output is correct |
| 15 |
Correct |
6 ms |
16732 KB |
Output is correct |
| 16 |
Correct |
8 ms |
16940 KB |
Output is correct |
| 17 |
Correct |
6 ms |
16732 KB |
Output is correct |
| 18 |
Correct |
7 ms |
16732 KB |
Output is correct |
| 19 |
Correct |
7 ms |
16784 KB |
Output is correct |
| 20 |
Correct |
7 ms |
16960 KB |
Output is correct |
| 21 |
Execution timed out |
6061 ms |
22868 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
