QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#343758 | #45. Tutte多项式 | FR | 100 ✓ | 1049ms | 364412kb | C++23 | 10.9kb | 2024-03-03 00:48:30 | 2024-03-03 00:48:31 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#pragma GCC target("popcnt")
typedef unsigned int uint;
typedef long long unsigned int uint64;
constexpr uint Mod = 998244353;
inline constexpr uint norm(const uint x)
{
return x < Mod ? x : x - Mod;
}
struct Z
{
uint v;
Z() { }
constexpr Z(const uint _v) : v(_v) { }
};
inline constexpr Z operator+(const Z x1, const Z x2) { return norm(x1.v + x2.v); }
inline constexpr Z operator-(const Z x1, const Z x2) { return norm(x1.v + Mod - x2.v); }
inline constexpr Z operator-(const Z x) { return x.v ? Mod - x.v : 0; }
inline constexpr Z operator*(const Z x1, const Z x2) { return static_cast<uint64>(x1.v) * x2.v % Mod; }
inline Z &operator+=(Z &x1, const Z x2) { return x1 = x1 + x2; }
inline Z &operator-=(Z &x1, const Z x2) { return x1 = x1 - x2; }
inline Z &operator*=(Z &x1, const Z x2) { return x1 = x1 * x2; }
inline Z Power(Z Base, int Exp) // constexpr
{
if (Exp < 0)
Exp += Mod - 1;
Z res = 1;
for (; Exp; Base *= Base, Exp >>= 1)
if (Exp & 1)
res *= Base;
return res;
}
inline Z Rec(const Z x) // constexpr
{
return Power(x, -1);
}
inline Z operator/(const Z x1, const Z x2) { return x1 * Rec(x2); } // constexpr
Z _Rec[22];
template<typename _Set_PS>
void zt(_Set_PS F, const int n)
{
for (int d = 1; d != 1 << n; d <<= 1)
for (int i = 0; i != 1 << n; i += d << 1)
for (int j = 0; j != d; ++j)
for (int k = 0; k <= n; ++k)
F[i + d + j][k] += F[i + j][k];
}
template<typename _Set_PS>
void zt_x(_Set_PS F, const int n)
{
for (int j = 0; j != 1 << (n - 1); ++j)
for (int k = 0; k <= n; ++k)
F[(1 << (n - 1)) + j][k] += F[j][k];
}
template<typename _Set_PS>
void mt(_Set_PS F, const int n)
{
for (int d = 1; d != 1 << n; d <<= 1)
for (int i = 0; i != 1 << n; i += d << 1)
for (int j = 0; j != d; ++j)
for (int k = 0; k <= n; ++k)
F[i + d + j][k] -= F[i + j][k];
}
template<typename _Set_PS>
void mt_x(_Set_PS F, const int n)
{
for (int j = 0; j != 1 << (n - 1); ++j)
for (int k = 0; k <= n; ++k)
F[(1 << (n - 1)) + j][k] -= F[j][k];
}
template<typename _Set_PS>
_Set_PS extract(_Set_PS F, const int s)
{
return reinterpret_cast<_Set_PS>(F[s] + __builtin_popcount(s));
}
template<int _Lim>
void Mult(const Z F[], const Z G[], int n, Z Res[])
{
static uint tmp[22];
if (n <= _Lim)
{
for (int i = 0; i <= n; ++i)
{
uint64 _tmp = 0;
for (int j = 0; j <= i; ++j)
_tmp += static_cast<uint64>(F[j].v) * G[i - j].v;
tmp[i] = _tmp % Mod;
}
}
else
{
for (int i = 0; i <= _Lim; ++i)
{
uint64 _tmp = 0;
for (int j = 0; j <= i; ++j)
_tmp += static_cast<uint64>(F[j].v) * G[i - j].v;
tmp[i] = _tmp % Mod;
}
for (int i = _Lim + 1; i <= n; ++i)
{
uint64 _tmp = 0;
for (int j = 0; j <= _Lim; ++j)
_tmp += static_cast<uint64>(F[j].v) * G[i - j].v;
_tmp %= Mod;
for (int j = _Lim + 1; j <= i; ++j)
_tmp += static_cast<uint64>(F[j].v) * G[i - j].v;
tmp[i] = _tmp % Mod;
}
}
std::copy(tmp, tmp + n + 1, Res);
}
void Mult(const Z F[], const Z G[], int n, Z Res[])
{
constexpr uint64 _Lim = ~0ULL / (Mod - 1) / (Mod - 1);
if (F[0].v <= ~0ULL / (Mod - 1) - _Lim * (Mod - 1))
Mult<_Lim + 1>(F, G, n, Res);
else
Mult<_Lim>(F, G, n, Res);
}
template<int _Lim>
void Div(const Z F[], const Z G[], int n, Z Res[])
{
static uint tmp[22];
const Z R = Rec(F[0]);
tmp[0] = (G[0] * R).v;
if (n <= _Lim)
{
for (int i = 1; i <= n; ++i)
{
uint64 _tmp = (~0ULL / Mod * Mod - Mod) + G[i].v;
for (int j = 1; j <= i; ++j)
_tmp -= static_cast<uint64>(F[j].v) * tmp[i - j];
tmp[i] = _tmp % Mod * R.v % Mod;
}
}
else
{
for (int i = 1; i <= _Lim; ++i)
{
uint64 _tmp = (~0ULL / Mod * Mod - Mod) + G[i].v;
for (int j = 1; j <= i; ++j)
_tmp -= static_cast<uint64>(F[j].v) * tmp[i - j];
tmp[i] = _tmp % Mod * R.v % Mod;
}
for (int i = _Lim + 1; i <= n; ++i)
{
uint64 _tmp = (~0ULL / Mod * Mod - Mod) + G[i].v;
for (int j = 1; j <= _Lim; ++j)
_tmp -= static_cast<uint64>(F[j].v) * tmp[i - j];
_tmp = (~0ULL / Mod * Mod - Mod) + _tmp % Mod;
for (int j = _Lim + 1; j <= i; ++j)
_tmp -= static_cast<uint64>(F[j].v) * tmp[i - j];
tmp[i] = _tmp % Mod * R.v % Mod;
}
}
std::copy(tmp, tmp + n + 1, Res);
}
void Div(const Z F[], const Z G[], int n, Z Res[])
{
constexpr uint64 _Lim = (~0ULL / Mod * Mod - Mod) / (Mod - 1) / (Mod - 1);
if ((G[0] / F[0]).v <= (~0ULL / Mod * Mod - Mod) / (Mod - 1) - _Lim * (Mod - 1))
Div<_Lim + 2>(F, G, n, Res);
else
Div<_Lim + 1>(F, G, n, Res);
}
template<typename _Set_PS_0, typename _Set_PS_1, typename _Set_PS_2>
void batch_Mult(const _Set_PS_0 T_F, const _Set_PS_1 T_G, int n, _Set_PS_2 T_Res)
{
for (int s = 0; s != 1 << n; ++s)
Mult(T_F[s], T_G[s], n, T_Res[s]);
}
template<typename _Set_PS_0, typename _Set_PS_1, typename _Set_PS_2>
void batch_Div(const _Set_PS_0 T_F, const _Set_PS_1 T_G, int n, _Set_PS_2 T_Res)
{
for (int s = 0; s != 1 << n; ++s)
Div(T_F[s], T_G[s], n, T_Res[s]);
}
template<typename _Set_PS>
void Exp(_Set_PS F, const int n)
{
F[0][0] = 1;
if (n == 0)
return;
for (int i = 1; i != n; ++i)
{
zt_x(F, i);
zt(extract(F, 1 << i), i);
batch_Mult(F, extract(F, 1 << i), i, extract(F, 1 << i));
}
mt(F, n - 1), mt(extract(F, 1 << (n - 1)), n - 1);
}
template<typename _Set_PS>
Z c_Exp(_Set_PS F, const int n)
{
if (n == 0)
return 1;
F[0][0] = 1;
for (int i = 1; i != n; ++i)
{
zt_x(F, i);
zt(extract(F, 1 << i), i);
batch_Mult(F, extract(F, 1 << i), i, extract(F, 1 << i));
}
Z res = 0;
for (int s = 1 << (n - 1); s != 1 << n; ++s)
res += (n - __builtin_popcount(s)) & 1 ? -F[s][n] : F[s][n];
return res;
}
template<typename _Set_PS>
void Log(_Set_PS F, const int n)
{
if (n == 0)
return;
zt(F, n - 1), zt(extract(F, 1 << (n - 1)), n - 1);
for (int i = n - 1; i; --i)
{
batch_Div(F, extract(F, 1 << i), i, extract(F, 1 << i));
mt(extract(F, 1 << i), i);
mt_x(F, i);
}
F[0][0] = 0;
}
template<typename _Set_PS>
Z c_Log(_Set_PS F, const int n)
{
if (n == 0)
return 0;
zt(F, n - 1), zt(extract(F, 1 << (n - 1)), n - 1);
batch_Div(F, extract(F, 1 << (n - 1)), n - 1, extract(F, 1 << (n - 1)));
Z res = 0;
for (int s = 1 << (n - 1); s != 1 << n; ++s)
res += (n ^ __builtin_parity(s)) & 1 ? -F[s][n] : F[s][n];
return res;
}
template<typename _Set_PS>
void Comp(_Set_PS F, const int n, const Z E[])
{
if (n == 0)
{
F[0][0] = E[0];
return;
}
static Z tmp[1 << 21][22];
for (int i = 0; i <= n; ++i)
extract(tmp, (1 << n) - (1 << (n - i)))[0][0] = E[i];
for (int i = 0; i != n; ++i)
{
zt(extract(F, 1 << i), i);
for (int j = 0; j != n - i; ++j)
{
batch_Mult(extract(tmp, (1 << n) - (1 << (n - (j + 1)))), extract(F, 1 << i), i, extract(tmp, (1 << n) - (1 << (n - j)) + (1 << i)));
if (i != n - 1)
zt_x(extract(tmp, (1 << n) - (1 << (n - j))), i + 1);
}
}
mt(tmp, n - 1), mt(extract(tmp, 1 << (n - 1)), n - 1);
for (int s = 1; s != 1 << n; ++s)
{
for (int i = 1; i != __builtin_popcount(s); ++i)
F[s][i] = 0;
F[s][__builtin_popcount(s)] = tmp[s][__builtin_popcount(s)];
}
}
template<typename _Set_PS>
Z c_Comp(_Set_PS F, const int n, const Z E[])
{
if (n == 0)
return E[0];
static Z tmp[1 << 21][22];
for (int i = 0; i <= n; ++i)
extract(tmp, (1 << n) - (1 << (n - i)))[0][0] = E[i];
for (int i = 0; i != n; ++i)
{
zt(extract(F, 1 << i), i);
for (int j = 0; j != n - i; ++j)
{
batch_Mult(extract(tmp, (1 << n) - (1 << (n - (j + 1)))), extract(F, 1 << i), i, extract(tmp, (1 << n) - (1 << (n - j)) + (1 << i)));
if (i != n - 1)
zt_x(extract(tmp, (1 << n) - (1 << (n - j))), i + 1);
}
}
for (int s = 0; s != 1 << n; ++s)
for (int i = 0; i != __builtin_popcount(s); ++i)
tmp[s][i] = 0;
Z res = 0;
for (int s = 1 << (n - 1); s != 1 << n; ++s)
res += (n ^ __builtin_parity(s)) & 1 ? -tmp[s][n] : tmp[s][n];
return res;
}
template<typename _Set_PS>
void Power(_Set_PS F, const int n, const int k)
{
static Z E[22];
for (int i = 0; i <= n; ++i)
E[i] = 0;
if (F[0][0].v != 0)
{
Z R = Rec(F[0][0]);
E[0] = Power(F[0][0], k);
for (int i = 1; i <= n && i <= k; ++i)
E[i] = E[i - 1] * R * (k - (i - 1));
}
else if (k <= n)
{
E[k] = 1;
for (int i = 1; i <= k; ++i)
E[k] *= i;
}
Comp(F, n, E);
}
template<typename _Set_PS>
Z c_Power(_Set_PS F, const int n, const int k)
{
static Z E[22];
for (int i = 0; i <= n; ++i)
E[i] = 0;
if (F[0][0].v != 0)
{
Z R = Rec(F[0][0]);
E[0] = Power(F[0][0], k);
for (int i = 1; i <= n && i <= k; ++i)
E[i] = E[i - 1] * R * (k - (i - 1));
}
else if (k <= n)
{
E[k] = 1;
for (int i = 1; i <= k; ++i)
E[k] *= i;
}
return c_Comp(F, n, E);
}
Z Tutte_c(const int G[], const int n, const int x, const int y)
{
static Z F[1 << 21][22];
for (int s = 0; s != 1 << n; ++s)
for (int i = 0; i <= n; ++i)
F[s][i] = 0;
if (y == 1)
{
F[1][1] = 1;
for (int i = 1; i != n; ++i)
{
for (int s = 0; s != 1 << i; ++s)
F[1 << i | s][__builtin_popcount(s)] = F[s][__builtin_popcount(s)] * __builtin_popcount(s & G[i]);
Exp(F + (1 << i), i);
for (int s = 0; s != 1 << i; ++s)
F[1 << i | s][__builtin_popcount(s) + 1] = F[1 << i | s][__builtin_popcount(s)], F[1 << i | s][__builtin_popcount(s)] = 0;
F[1 << i][1] = 1;
}
if (x == 1)
return F[(1 << n) - 1][n];
for (int s = 0; s != 1 << n; ++s)
F[s][__builtin_popcount(s)] = F[s][__builtin_popcount(s)] * (Z(x) - 1);
return Rec(Z(x) - 1) * c_Exp(F, n);
}
F[0][0] = 1;
for (int s = 1; s != 1 << n; ++s)
{
uint cnt = 0;
for (int t = s; t; t &= t - 1)
cnt += __builtin_popcount(G[__builtin_ctz(t)] & t);
F[s][__builtin_popcount(s)] = Power(y, cnt);
}
if (x == 1)
return Power(Z(y) - 1, 1 - n) * c_Log(F, n);
return Rec(Z(x) - 1) * Power(Z(y) - 1, -n) * c_Power(F, n, ((Z(x) - 1) * (Z(y) - 1)).v);
}
Z Tutte(const int G[], const int n, const int x, const int y)
{
int r = (1 << n) - 1;
Z res = 1;
while (r)
{
int s, ts = r & -r;
do
{
s = ts;
for (int t = s; t; t &= t - 1)
ts |= G[__builtin_ctz(t)];
} while (ts != s);
static int tmp[21];
for (int i = 0; i != __builtin_popcount(s); ++i)
tmp[i] = 0;
for (int ti = s, i = 0; ti; ti &= ti - 1, ++i)
for (int tj = s, j = 0; tj; tj &= tj - 1, ++j)
tmp[i] |= (G[__builtin_ctz(ti)] >> __builtin_ctz(tj) & 1) << j;
res = res * Tutte_c(tmp, __builtin_popcount(s), x, y);
r &= ~s;
}
return res;
}
int main(int argc, char **argv)
{
static int N, x, y, G[21];
scanf("%d", &N);
_Rec[1] = 1;
for (int i = 2; i <= N; ++i)
_Rec[i] = (Mod - Mod / i) * _Rec[Mod % i];
for (int i = 0, f; i != N; ++i)
for (int j = 0; j != N; ++j)
scanf("%d", &f), G[i] |= f << j;
scanf("%d %d", &x, &y);
printf("%u\n", Tutte(G, N, x, y).v);
return 0;
}
详细
Subtask #1:
score: 16
Accepted
Test #1:
score: 16
Accepted
time: 1ms
memory: 3856kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1
output:
6
result:
ok answer is 6
Test #2:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 2
output:
24
result:
ok answer is 24
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
output:
10
result:
ok answer is 10
Test #4:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1
output:
24
result:
ok answer is 24
Test #5:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 2
output:
52
result:
ok answer is 52
Test #6:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 2 0
output:
60
result:
ok answer is 60
Test #7:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 2 1
output:
86
result:
ok answer is 86
Test #8:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1
output:
3
result:
ok answer is 3
Test #9:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 20020221
output:
20020223
result:
ok answer is 20020223
Test #10:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 20020814 1
output:
807453860
result:
ok answer is 807453860
Test #11:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
7 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 20020814 20020221
output:
307912635
result:
ok answer is 307912635
Test #12:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1
output:
24
result:
ok answer is 24
Test #13:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 20020221
output:
98439924
result:
ok answer is 98439924
Test #14:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 20020814 1
output:
705719054
result:
ok answer is 705719054
Test #15:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
7 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 20020814 20020221
output:
485607933
result:
ok answer is 485607933
Test #16:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
7 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1
output:
48
result:
ok answer is 48
Test #17:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
7 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 20020221
output:
815810322
result:
ok answer is 815810322
Test #18:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
7 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 20020814 1
output:
387261289
result:
ok answer is 387261289
Test #19:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
7 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 20020814 20020221
output:
895603904
result:
ok answer is 895603904
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #20:
score: 20
Accepted
time: 1ms
memory: 4092kb
input:
11 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 20020221
output:
153595675
result:
ok answer is 153595675
Test #21:
score: 0
Accepted
time: 1ms
memory: 4112kb
input:
11 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 20020814 1
output:
491253731
result:
ok answer is 491253731
Test #22:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
11 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 20020814 20020221
output:
17689848
result:
ok answer is 17689848
Subtask #3:
score: 14
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #23:
score: 14
Accepted
time: 0ms
memory: 10220kb
input:
14 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0...
output:
171192566
result:
ok answer is 171192566
Test #24:
score: 0
Accepted
time: 5ms
memory: 6512kb
input:
14 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0...
output:
858770596
result:
ok answer is 858770596
Test #25:
score: 0
Accepted
time: 4ms
memory: 6884kb
input:
14 0 0 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1...
output:
220200163
result:
ok answer is 220200163
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #26:
score: 25
Accepted
time: 87ms
memory: 26964kb
input:
18 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0...
output:
150803960
result:
ok answer is 150803960
Test #27:
score: 0
Accepted
time: 95ms
memory: 27568kb
input:
18 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1...
output:
295845902
result:
ok answer is 295845902
Test #28:
score: 0
Accepted
time: 73ms
memory: 49544kb
input:
18 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1...
output:
82075728
result:
ok answer is 82075728
Subtask #5:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #29:
score: 25
Accepted
time: 943ms
memory: 185884kb
input:
21 0 0 0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0...
output:
794685740
result:
ok answer is 794685740
Test #30:
score: 0
Accepted
time: 1049ms
memory: 185164kb
input:
21 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1...
output:
584501085
result:
ok answer is 584501085
Test #31:
score: 0
Accepted
time: 797ms
memory: 364412kb
input:
21 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0...
output:
114086868
result:
ok answer is 114086868