QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#706541 | #9563. 人间应又雪 | TheZone | 0 | 0ms | 0kb | C++20 | 4.0kb | 2024-11-03 12:06:58 | 2024-11-03 12:06:59 |
answer
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
#define double long double
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;
const int N = 15;
const int M = 2e5 + 5;
int n, S, flg;
int pw[N], op[3][3], top[3][3];
struct poly {
ll a, b, c; // a + bx + cx ^ 2
poly () : a(0), b(0), c(0) { }
poly (ll _a, ll _b, ll _c) : a(_a), b(_b), c(_c) { }
poly (ll x) : a(x), b(0), c(0) { }
poly operator + (const poly &r) const {
return poly(a + r.a, b + r.b, c + r.c);
}
poly operator - (const poly &r) const {
return poly(a - r.a, b - r.b, c - r.c);
}
poly operator * (const poly &r) const {
return poly(a * r.a + b * r.c + c * r.b, a * r.b + r.a * b + c * r.c, a * r.c + b * r.b + c * r.a);
}
ll val() {
return a - b / 2 - c / 2;
}
bool operator == (const poly &r) const {
return (a == r.a) && (b == r.b) && (c == r.c);
}
};
const poly W[3] = {
poly(1, 0, 0),
poly(0, 1, 0),
poly(0, 0, 1)
};
poly f[N][M], g[N][M], h[N][M];
poly a[5][3], b[5][3], c[5][3];
void FWT(int d) {
if (d == 1) {
F (i, 0, 2) {
h[d][i] = ll(0);
}
F (i, 0, 2) {
F (j, 0, 2) {
h[d][op[i][j]] = h[d][op[i][j]] + f[d][i] * g[d][j];
}
}
return;
}
F (i, 0, pw[d] - 1) {
h[d][i] = ll(0);
}
int k = pw[d - 1];
F (t, 0, 4) {
F (i, 0, k - 1) {
f[d - 1][i] = f[d][i] * a[t][0] + f[d][i + k] * a[t][1] + f[d][i + 2 * k] * a[t][2];
g[d - 1][i] = g[d][i] * b[t][0] + g[d][i + k] * b[t][1] + g[d][i + 2 * k] * b[t][2];
}
FWT(d - 1);
F (i, 0, k - 1) {
h[d][i] = h[d][i] + h[d - 1][i] * c[t][0];
h[d][i + k] = h[d][i + k] + h[d - 1][i] * c[t][1];
h[d][i + 2 * k] = h[d][i + 2 * k] + h[d - 1][i] * c[t][2];
}
}
}
bool chk(int o) {
int fl = 0;
F (A, 0, 26) {
F (B, 0, 26) {
F (C, 0, 26) {
if (fl) {
break;
}
int u[3], v[3], w[3];
F (i, 0, 2) {
u[i] = A / pw[i] % 3;
v[i] = B / pw[i] % 3;
w[i] = C / pw[i] % 3;
}
auto gt = [&](int i, int j) {
if (!o) {
return w[(u[i] + v[j]) % 3];
} else {
return w[max(u[i], v[j])];
}
};
int df = 0;
F (i, 0, 2) {
F (j, 0, 2) {
top[i][j] = gt(i, j);
if (top[i][j] != op[i][j]) {
df++;
}
}
}
if (df > 2) {
continue;
}
fl = 1;
F (i, 0, 2) {
F (j, 0, 2) {
if (!o) {
a[i][j] = W[u[j] * i % 3];
b[i][j] = W[v[j] * i % 3];
c[i][w[j]] = c[i][w[j]] + W[(3 - i * j % 3) % 3];
} else {
a[i][j] = ll(u[j] <= i);
b[i][j] = ll(v[j] <= i);
if (i == j) {
c[i][w[j]] = c[i][w[j]] + 1;
}
if (i + 1 == j) {
c[i][w[j]] = c[i][w[j]] - 1;
}
}
}
}
int t = 3;
F (i, 0, 2) {
F (j, 0, 2) {
if (top[i][j] == op[i][j]) {
continue;
}
a[t][i] = 1;
b[t][j] = 1;
c[t][top[i][j]] = (flg ? -1 : -3);
c[t][op[i][j]] = (flg ? 1 : 3);
t++;
}
}
}
}
}
return fl;
}
void solve() {
F (i, 0, 2) {
F (j, 0, 2) {
cin >> op[i][j];
}
}
cin >> n;
pw[0] = 1;
F (i, 1, 11) {
pw[i] = pw[i - 1] * 3;
}
if (!chk(0)) {
flg = 1;
assert(chk(1));
}
S = pw[n];
F (i, 0, S - 1) {
cin >> f[n][i].a;
}
F (i, 0, S - 1) {
cin >> g[n][i].a;
}
FWT(n);
F (i, 0, S - 1) {
cout << h[n][i].val() / (flg ? 1 : pw[n - 1]) << ' ';
}
}
bool Med;
int main() {
// FIO("A");
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}
詳細信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
1000 1 9 8 0 8 5 2 1 6 4 5 1 5 9 8 0 1 7 3 2 0 8 5 1 0 8 9 0 3 8 7 3 2 4 9 9 8 9 0 8 3 9 3 9 8 3 4 9 10 0 0 9 5 5 4 3 6 10 5 8 8 0 3 5 1 6 8 4 2 5 8 9 0 5 2 3 8 1 4 2 9 10 8 0 2 8 2 3 1 7 0 1 5 1 8 9 0 1 0 4 9 9 5 7 2 9 10 0 3 4 0 10 0 9 6 7 0 8 9 0 4 8 4 4 0 4 2 3 9 8 0 0 5 2 3 1 0 4 0 0 10 10 0 3 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #3:
score: 0
Runtime Error
input:
1000 2 10 2 3 1 2 1 2 1 2 2 1 0 1 10 2 0 0 0 0 0 0 0 0 0 0 0 10 2 3 0 0 1 1 0 1 0 0 0 1 10 2 3 0 0 0 0 0 0 0 0 0 0 10 2 1 1 0 2 2 0 0 1 0 1 1 10 2 3 0 1 1 0 2 0 1 2 2 2 10 2 0 0 0 0 0 0 0 0 0 0 0 10 2 0 0 0 0 1 1 1 0 0 0 1 10 2 1 1 1 0 2 0 0 0 0 0 0 10 2 1 1 1 2 0 0 2 0 2 1 0 10 2 1 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #6:
score: 0
Runtime Error
input:
10 3 5 5 3 4 1 5 1 4 4 5 4 2 2 3 4 5 5 0 1 1 5 3 4 4 4 2 2 1 0 1 3 5 3 0 2 3 5 4 2 3 2 4 1 4 3 4 4 3 2 2 3 4 5 4 0 2 3 5 3 1 0 5 5 4 0 2 0 4 1 3
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Runtime Error
Test #33:
score: 0
Runtime Error
input:
5000 7 19 19 16 4 12 5 15 12 11 9 0 3 1 8 4 17 2 19 3 5 4 1 18 20 19 18 14 12 16 7 14 2 3 13 4 4 6 8 1 16 19 10 20 20 19 3 15 7 5 16 19 0 1 19 10 19 13 17 18 5 1 13 9 4 8 15 19 20 6 8 3 0 12 4 13 19 2 6 4 11 8 17 6 8 13 11 8 20 18 19 19 3 15 19 12 17 11 11 2 4 4 16 13 10 12 15 14 3 10 19 20 20 12 15...
output:
result:
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%
Subtask #10:
score: 0
Skipped
Dependency #2:
0%