QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #444616 | #8526. Polygon II | ucup-team3510# | AC ✓ | 1346ms | 12768kb | C++20 | 2.2kb | 2024-06-15 20:23:59 | 2024-06-15 20:23:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 1100, mod = 1e9 + 7;
int dp[55][2205][2], f[4205][2], pw[1005], fac[1005], inv[1005];
int ww[1005][1005];
int cnt[55], C[1005][1005];
int qpow(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1)
ans = (ll)ans * x % mod;
x = (ll)x * x % mod;
y >>= 1;
}
return ans;
}
int F(int x, int y) // x [0,1) <= y
{
int i, ans = 0, tmp;
if(y > x)
return 1;
for(i = 0; i <= y; i++)
{
tmp = (ll)C[x][i] * ww[y - i][x] % mod * inv[x] % mod;
if(i & 1)
ans = (ans + mod - tmp) % mod;
else
ans = (ans + tmp) % mod;
}
return ans;
}
int main()
{
int n, i, j, k, c, a, ans = 0, tot = 0;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
scanf("%d", &a);
for(j = 0; j <= a; j++)
cnt[j]++;
tot += a;
}
for(i = 0; i <= n; i++)
{
C[i][0] = 1;
for(j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
pw[0] = 1;
for(i = 1; i <= n; i++)
pw[i] = pw[i - 1] * ((mod + 1ll) / 2) % mod;
fac[0] = 1;
for(i = 1; i <= n; i++)
fac[i] = (ll)fac[i - 1] * i % mod;
for(i = 0; i <= n; i++)
inv[i] = qpow(fac[i], mod - 2);
for(i = 0; i <= n; i++)
{
ww[i][0] = 1;
for(j = 1; j <= n; j++)
ww[i][j] = (ll)ww[i][j - 1] * i % mod;
}
dp[51][B][0] = 1;
for(i = 50; i >= 1; i--)
{
for(j = -2 * B; j <= 2 * B; j += 2)
{
for(k = 0; k <= cnt[i]; k++)
{
c = max(min(j + k + B, 2 * B), 0);
dp[i][c][0] = (dp[i][c][0] + (ll)dp[i + 1][j / 2 + B][0] * C[cnt[i]][k]) % mod;
}
for(k = 0; k < cnt[i]; k++)
{
c = max(min(j + k + B, 2 * B), 0);
dp[i][c][1] = (dp[i][c][1] + ((ll)dp[i + 1][j / 2 + B][0] * (cnt[i] - cnt[i + 1]) + dp[i + 1][j / 2 + B][1]) % mod * C[cnt[i] - 1][k] % mod) % mod;
c = max(min(j + k - 1 + B, 2 * B), 0);
dp[i][c][1] = (dp[i][c][1] + ((ll)dp[i + 1][j / 2 + B][0] * (cnt[i] - cnt[i + 1]) + dp[i + 1][j / 2 + B][1]) % mod * C[cnt[i] - 1][k] % mod) % mod;
}
}
}
for(j = -B; j <= B; j++)
ans = (ans + (ll)F(n, 1 - j) * (dp[1][j + B][1] + (ll)(cnt[0] - cnt[1]) * dp[1][j + B][0] % mod)) % mod;
ans = (ll)ans * qpow(2, mod - 1 - tot) % mod;
ans = (mod + 1 - ans) % mod;
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8380kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 0ms
memory: 6764kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 0ms
memory: 8888kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 0ms
memory: 6836kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 4ms
memory: 7924kb
input:
10 39 11 25 1 12 44 10 46 27 15
output:
913863330
result:
ok 1 number(s): "913863330"
Test #6:
score: 0
Accepted
time: 45ms
memory: 6964kb
input:
57 43 22 3 16 7 5 24 32 25 16 41 28 24 30 28 10 32 48 41 43 34 37 48 34 3 9 21 41 49 25 2 0 36 45 34 33 45 9 42 29 43 9 38 34 44 33 44 6 46 39 22 36 40 37 19 34 3
output:
400729664
result:
ok 1 number(s): "400729664"
Test #7:
score: 0
Accepted
time: 57ms
memory: 7228kb
input:
100 44 32 6 6 6 44 12 32 6 9 23 12 14 23 12 14 23 49 6 14 32 23 49 9 32 24 23 6 32 6 49 23 12 44 24 9 14 6 24 44 24 23 44 44 49 32 49 12 49 49 24 49 12 23 3 14 6 3 3 6 12 3 49 24 49 24 24 32 23 32 49 14 3 24 49 3 32 14 44 24 49 3 32 23 49 44 44 9 23 14 49 9 3 6 44 24 3 3 12 44
output:
32585394
result:
ok 1 number(s): "32585394"
Test #8:
score: 0
Accepted
time: 263ms
memory: 12652kb
input:
1000 2 27 0 0 27 0 2 0 27 0 27 27 0 0 0 0 0 2 0 27 0 2 2 0 27 27 0 0 0 27 2 2 2 27 0 2 27 2 0 2 27 0 0 27 0 27 0 0 27 2 27 2 2 27 2 27 0 0 27 0 27 0 2 27 2 2 0 27 27 27 27 0 27 0 27 0 2 2 0 2 2 27 0 0 27 0 0 27 0 2 27 27 2 27 2 0 0 2 27 27 27 27 27 27 2 2 0 2 2 0 2 2 0 27 0 27 2 2 0 27 27 0 0 27 2 2...
output:
94588769
result:
ok 1 number(s): "94588769"
Test #9:
score: 0
Accepted
time: 811ms
memory: 12708kb
input:
1000 40 14 47 3 32 18 3 49 22 23 32 18 23 24 18 32 23 39 32 27 49 49 22 50 50 22 23 47 14 47 50 32 22 24 49 49 18 22 18 22 50 3 32 47 40 3 39 22 24 47 32 49 49 22 32 39 14 49 39 3 32 22 24 18 39 49 24 18 40 23 23 49 39 39 18 39 27 49 14 27 27 14 18 24 39 22 40 50 18 18 18 39 39 18 23 23 22 3 49 47 2...
output:
626481946
result:
ok 1 number(s): "626481946"
Test #10:
score: 0
Accepted
time: 632ms
memory: 12636kb
input:
1000 28 32 35 9 21 11 43 23 45 15 23 2 8 3 39 41 31 9 45 35 27 14 40 28 31 9 31 9 9 40 8 6 27 43 3 27 23 49 27 6 28 25 11 9 15 27 38 27 12 28 25 2 15 27 45 6 27 1 21 38 1 25 27 21 49 31 31 14 39 39 8 39 40 28 15 31 21 14 43 38 11 8 8 23 9 11 15 2 11 39 32 14 28 15 40 49 27 9 23 9 9 6 21 2 2 1 14 11 ...
output:
644443122
result:
ok 1 number(s): "644443122"
Test #11:
score: 0
Accepted
time: 679ms
memory: 12712kb
input:
972 39 15 23 0 40 29 43 47 6 9 30 9 2 8 19 9 45 25 26 38 33 18 6 33 44 48 24 8 4 16 33 42 33 31 36 33 13 16 3 12 21 19 1 30 24 23 43 35 0 33 31 32 23 31 36 12 26 0 29 48 28 33 28 28 3 49 9 5 29 8 29 28 49 41 33 49 5 49 6 9 50 25 39 11 1 36 6 44 10 34 32 31 25 31 36 36 3 9 50 35 47 43 25 46 30 18 5 2...
output:
684920840
result:
ok 1 number(s): "684920840"
Test #12:
score: 0
Accepted
time: 108ms
memory: 12724kb
input:
147 34 47 42 23 46 3 41 9 15 42 21 32 24 1 19 46 29 35 38 20 2 43 36 47 19 23 20 9 6 28 48 46 45 21 19 41 31 36 50 7 11 25 0 43 38 46 21 2 26 40 32 14 45 35 47 21 13 26 26 30 3 36 35 45 36 21 21 25 2 40 35 50 23 3 16 44 40 42 6 37 36 19 20 14 30 47 13 49 47 45 26 12 15 21 42 30 19 5 21 9 28 8 3 34 4...
output:
972735235
result:
ok 1 number(s): "972735235"
Test #13:
score: 0
Accepted
time: 664ms
memory: 12580kb
input:
1000 36 15 9 5 35 37 17 30 24 13 18 32 14 35 36 26 23 7 21 15 43 15 21 11 33 33 9 16 5 26 1 45 48 27 20 20 20 48 42 27 22 7 39 35 11 38 33 47 22 34 43 4 32 0 47 35 48 8 9 3 40 3 27 22 20 43 12 37 30 18 2 37 37 35 44 3 42 14 20 24 44 5 17 38 46 41 28 23 21 7 13 15 35 38 21 14 6 37 37 6 13 34 32 13 23...
output:
179933029
result:
ok 1 number(s): "179933029"
Test #14:
score: 0
Accepted
time: 685ms
memory: 12740kb
input:
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7...
output:
540327646
result:
ok 1 number(s): "540327646"
Test #15:
score: 0
Accepted
time: 693ms
memory: 12768kb
input:
1000 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 46 46 46 46 46 46 46 46 46 46 46 46 46 4...
output:
169647494
result:
ok 1 number(s): "169647494"
Test #16:
score: 0
Accepted
time: 1310ms
memory: 12652kb
input:
1000 11 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 40 50 50 50 50 50 21 50 12 50 50 50 50 50 0 50 50 50 38 50 50 50 50 50 50 25 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 7 50 50 50 50 50 50 50 50 ...
output:
862643524
result:
ok 1 number(s): "862643524"
Test #17:
score: 0
Accepted
time: 1346ms
memory: 12728kb
input:
1000 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...
output:
819612372
result:
ok 1 number(s): "819612372"
Test #18:
score: 0
Accepted
time: 1342ms
memory: 12604kb
input:
1000 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...
output:
18215579
result:
ok 1 number(s): "18215579"
Test #19:
score: 0
Accepted
time: 5ms
memory: 8392kb
input:
16 0 2 24 1 23 9 14 17 28 29 25 27 15 19 11 20
output:
115090079
result:
ok 1 number(s): "115090079"
Test #20:
score: 0
Accepted
time: 10ms
memory: 12640kb
input:
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
819612372
result:
ok 1 number(s): "819612372"
Test #21:
score: 0
Accepted
time: 6ms
memory: 6912kb
input:
18 9 4 21 5 22 6 9 16 3 14 11 2 0 12 6 3 7 21
output:
0
result:
ok 1 number(s): "0"
Extra Test:
score: 0
Extra Test Passed