QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477854#45. Tutte多项式NOI_AK_ME#100 ✓2149ms184168kbC++209.7kb2024-07-14 11:45:282024-07-14 11:45:29

Judging History

你现在查看的是最新测评结果

  • [2024-07-14 11:45:29]
  • 评测
  • 测评结果:100
  • 用时:2149ms
  • 内存:184168kb
  • [2024-07-14 11:45:28]
  • 提交

answer

#include <cstdio>

#pragma GCC target("popcnt")

typedef unsigned int uint;
typedef long long unsigned int uint64;

const uint Mod = 998244353;

inline uint norm(const uint x) {
    return x < Mod ? x : x - Mod;
}

struct Z {
    uint v;
    Z() { }
    Z(const uint _v) : v(_v) { }
};

inline Z operator+(const Z x1, const Z x2) {
    return norm(x1.v + x2.v);
}
inline Z operator-(const Z x1, const Z x2) {
    return norm(x1.v + Mod - x2.v);
}
inline Z operator-(const Z x) {
    return x.v ? Mod - x.v : 0;
}
inline 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) {
    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) {
    return Power(x, -1);
}

Z _Rec[22];

void zt(Z F[1 << 21][22], 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];
}

void mt(Z F[1 << 21][22], 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];
}

void Exp(const Z A[22], int n, Z res[22]) {
    static uint tmp[22];
    res[0] = 1;

    if (n <= 18) {
        for (int i = 1; i <= n; ++i) {
            tmp[i] = (i * A[i]).v;
            uint64 _tmp = 0;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            res[i] = _Rec[i] * (_tmp % Mod);
        }
    } else {
        for (int i = 1; i <= 18; ++i) {
            tmp[i] = (i * A[i]).v;
            uint64 _tmp = 0;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            res[i] = _Rec[i] * (_tmp % Mod);
        }

        for (int i = 19; i <= n; ++i) {
            tmp[i] = (i * A[i]).v;
            uint64 _tmp = 0;

            for (int j = 1; j <= 18; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            _tmp %= Mod;

            for (int j = 19; j <= i; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            res[i] = _Rec[i] * (_tmp % Mod);
        }
    }
}

void Exp(Z F[1 << 21][22], const int n) {
    zt(F, n);

    for (int s = 0; s != 1 << n; ++s)
        Exp(F[s], n, F[s]);

    mt(F, n);
}

Z c_Exp(Z F[1 << 21][22], const int n) {
    Z res = 0;
    zt(F, n);

    for (int s = 0; s != 1 << n; ++s)
        Exp(F[s], n, F[s]), res += (n - __builtin_popcount(s)) & 1 ? -F[s][n] : F[s][n];

    return res;
}

void Log(const Z A[22], int n, Z res[22]) {
    static uint nA[22];

    for (int i = 0; i <= n; ++i)
        nA[i] = (-A[i]).v;

    static uint tmp[22];
    tmp[0] = 0;

    if (n <= 17) {
        for (int i = 1; i <= n; ++i) {
            uint64 _tmp = static_cast<uint64>(i) * A[i].v;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            tmp[i] = _tmp % Mod;
        }
    } else {
        for (int i = 1; i <= 17; ++i) {
            uint64 _tmp = static_cast<uint64>(i) * A[i].v;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            tmp[i] = _tmp % Mod;
        }

        for (int i = 18; i <= n; ++i) {
            uint64 _tmp = static_cast<uint64>(i) * A[i].v;

            for (int j = 1; j <= 17; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            _tmp %= Mod;

            for (int j = 18; j <= i; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            tmp[i] = _tmp % Mod;
        }
    }

    for (int i = 0; i <= n; ++i)
        res[i] = _Rec[i] * tmp[i];
}

Z c_Log(Z F[1 << 21][22], const int n) {
    Z res = 0;
    zt(F, n);

    for (int s = 0; s != 1 << n; ++s)
        Log(F[s], n, F[s]), res += (n - __builtin_popcount(s)) & 1 ? -F[s][n] : F[s][n];

    return res;
}

void Power(const Z A[22], int n, uint exp, Z res[22]) {
    static uint nA[22];

    for (int i = 0; i <= n; ++i)
        nA[i] = (-A[i]).v;

    static uint tmp[22];
    tmp[0] = 0;

    if (n <= 17) {
        for (int i = 1; i <= n; ++i) {
            uint64 _tmp = static_cast<uint64>(i) * A[i].v;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            tmp[i] = _tmp % Mod;
        }
    } else {
        for (int i = 1; i <= 17; ++i) {
            uint64 _tmp = static_cast<uint64>(i) * A[i].v;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            tmp[i] = _tmp % Mod;
        }

        for (int i = 18; i <= n; ++i) {
            uint64 _tmp = static_cast<uint64>(i) * A[i].v;

            for (int j = 1; j <= 17; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            _tmp %= Mod;

            for (int j = 18; j <= i; ++j)
                _tmp += static_cast<uint64>(nA[j]) * tmp[i - j];

            tmp[i] = _tmp % Mod;
        }
    }

    for (int i = 1; i <= n; ++i)
        tmp[i] = (Z(tmp[i]) * exp).v;

    res[0] = 1;

    if (n <= 18) {
        for (int i = 1; i <= n; ++i) {
            uint64 _tmp = 0;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            res[i] = _Rec[i] * (_tmp % Mod);
        }
    } else {
        for (int i = 1; i <= 18; ++i) {
            uint64 _tmp = 0;

            for (int j = 1; j <= i; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            res[i] = _Rec[i] * (_tmp % Mod);
        }

        for (int i = 19; i <= n; ++i) {
            uint64 _tmp = 0;

            for (int j = 1; j <= 18; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            _tmp %= Mod;

            for (int j = 19; j <= i; ++j)
                _tmp += static_cast<uint64>(tmp[j]) * res[i - j].v;

            res[i] = _Rec[i] * (_tmp % Mod);
        }
    }

    /*
    static Z tmp[22];
    tmp[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        Z _tmp = 0, coef = -Z(i);
        for (int j = 1; j <= i; ++j)
            coef += exp + 1, _tmp += coef * A[j] * tmp[i - j];
        tmp[i] = _tmp * _Rec[i];
    }
    for (int i = 0; i <= n; ++i)
        res[i] = tmp[i];
    */
}

Z c_Power(Z F[1 << 21][22], const int n, const uint exp) {
    Z res = 0;
    zt(F, n);

    for (int s = 0; s != 1 << n; ++s)
        Power(F[s], n, exp, F[s]), res += (n - __builtin_popcount(s)) & 1 ? -F[s][n] : F[s][n];

    return res;
}

Z Tutte_c(const int G[], const int n, const int x, const int y) {
    static Z F[1 << 21][22];

    for (int s = 1; 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 N, x, y, G[21];

int main(int argc, char **argv) {
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 16
Accepted

Test #1:

score: 16
Accepted
time: 0ms
memory: 3760kb

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: 0ms
memory: 3760kb

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: 3872kb

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: 0ms
memory: 3740kb

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: 3796kb

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: 3760kb

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: 3760kb

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: 3816kb

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: 3796kb

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: 3956kb

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: 3884kb

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: 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 1

output:

24

result:

ok answer is 24

Test #13:

score: 0
Accepted
time: 0ms
memory: 3796kb

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: 3952kb

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: 3884kb

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: 3880kb

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: 3960kb

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: 3960kb

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: 0ms
memory: 3880kb

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: 4064kb

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: 3992kb

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: 4064kb

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: 7ms
memory: 5168kb

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: 4ms
memory: 5284kb

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: 9ms
memory: 7312kb

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: 88ms
memory: 27036kb

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: 184ms
memory: 26528kb

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: 143ms
memory: 27012kb

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: 993ms
memory: 183984kb

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: 2149ms
memory: 184168kb

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: 1471ms
memory: 184092kb

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