QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343758#45. Tutte多项式FR100 ✓1049ms364412kbC++2310.9kb2024-03-03 00:48:302024-03-03 00:48:31

Judging History

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

  • [2024-03-03 00:48:31]
  • 评测
  • 测评结果:100
  • 用时:1049ms
  • 内存:364412kb
  • [2024-03-03 00:48:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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