QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#526602 | #6132. Repair the Artwork | RPChe_ | WA | 1162ms | 18968kb | C++14 | 2.5kb | 2024-08-21 18:12:51 | 2024-08-21 18:12:52 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105, mod = 1e9 + 7;
int n, m, a[N], ans, f[N][2][N * N], b[N], tot;
int qpow(int a, int b = mod - 2) {
int res = 1;
while (b) {
if (b & 1) (res *= a) %= mod;
(a *= a) %= mod, b >>= 1;
}
return res;
}
void add(int &x, int y) {
x += y;
if (abs(x) > 1e15) x %= mod;
}
void solve() {
for (int i = 0; i <= tot; i++) {
int lim = b[i] * (b[i] - 1) / 2 + b[i];
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= lim; k++) {
f[i][j][k] = 0;
}
}
}
f[0][0][0] = 1;
for (int i = 0; i < tot; i++) {
int lim = (b[i] - 1) * b[i] / 2 + b[i];
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= lim; k++) {
if (!f[i][j][k]) continue;
for (int l = i + 1; l <= tot; l++) {
int len = b[l] - b[i] - 1;
if (a[b[l]] == 1) {
add(f[l][j][k + len * (len - 1) / 2 + len], f[i][j][k]);
break;
} else {
add(f[l][!j][k + len * (len - 1) / 2 + len], f[i][j][k]);
}
}
}
}
}
ans = 0;
for (int i = tot; i >= 0; i--) {
int lim = (b[i] - 1) * b[i] / 2 + b[i];
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= lim; k++) {
int rst = n - b[i];
rst = rst * (rst - 1) / 2 + rst;
if (j & 1) {
// add(ans, -f[i][j][k] * qpow(k + rst, m) % mod);
// ans %= mod;
(ans -= 1ll * f[i][j][k] * qpow(k + rst, m) % mod) %= mod;
} else {
// add(ans, f[i][j][k] * qpow(k + rst, m) % mod);
// ans %= mod;
(ans += 1ll * f[i][j][k] * qpow(k + rst, m) % mod) %= mod;
}
}
}
if (a[b[i]] == 1) break;
}
ans = (ans % mod + mod) % mod;
}
signed main() {
int T; scanf("%lld", &T);
while (T--) {
scanf("%lld%lld", &n, &m);
tot = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
if (a[i]) b[++tot] = i;
}
solve();
printf("%lld\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3896kb
input:
3 2 2 2 0 3 2 2 1 0 3 1 2 1 0
output:
8 3 1
result:
ok 3 number(s): "8 3 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 12012kb
input:
100 2 1 0 1 2 1 2 1 2 1 1 1 1 6 2 1 14 2 3 12 2 2 2 6 13 2 2 0 2 0 2 7 14 0 0 0 0 2 2 0 5 8 2 2 0 0 0 5 5 2 2 0 0 0 12 3 0 2 0 2 2 0 1 2 2 2 2 0 7 11 2 2 0 1 0 1 0 4 4 2 1 2 2 7 5 1 1 0 0 1 0 0 2 14 2 1 15 17 2 2 1 2 0 0 0 0 2 0 1 0 0 0 0 15 11 1 1 2 0 1 2 0 0 1 0 2 1 1 1 1 15 18 1 0 1 0 2 2 1 2 0 1...
output:
1 1 0 1 1 175715347 833406719 467966815 458805426 650344 2208 537089254 146 7776 1 703335050 123067364 355668256 487954758 53774922 544070885 436748805 369291507 760487845 513270785 501075264 487417783 464534262 979007529 137956839 143317512 648268264 851188473 702545117 946416372 595191705 35054850...
result:
ok 100 numbers
Test #3:
score: -100
Wrong Answer
time: 1162ms
memory: 18968kb
input:
1000 20 673037423 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 774964932 2 2 2 17 730319736 2 2 1 1 2 2 2 2 2 2 2 2 2 1 2 2 1 11 893285699 2 2 2 1 2 1 2 2 2 1 2 16 98149251 1 2 1 2 1 2 1 1 2 1 2 2 2 2 1 2 7 556953277 1 2 2 1 2 2 2 3 228111342 1 1 1 11 640995044 2 2 1 1 2 2 1 1 1 1 1 19 741419324 1 1 2 ...
output:
447486147 204414804 452414918 684654914 763978130 805973365 0 922180033 214948715 401017738 0 201368027 752718484 611006275 848004989 391560729 950934074 202096866 443534870 24665646 482580424 321199514 922369975 152629767 5546104 1 194145234 1 1 1 562381239 648246425 497517379 217016206 961507095 4...
result:
wrong answer 298th numbers differ - expected: '711944173', found: '294288174'