XX Open Cup, Grand Prix of Zhejiang(Yuhao Du Contest 7)

X

Contest Link: https://official.contest.yandex.ru/opencupXX/contest/17333

A. Alternative Account

签到题.直接手动容斥一下就过了.

#include <bits/stdc++.h>

const int N = 1e5 + 50;

inline int popcount(unsigned long long x)
{
	return __builtin_popcount(x >> 32) + __builtin_popcount(x & ~0u);
}

struct set
{
	uint64_t data[N >> 6];
	int n, m;
	
	inline void clear()
	{
		memset(data, 0, (m + 1) * sizeof(uint64_t));
	}
	bool operator[] (int k) const
	{
		int idx = k >> 6, bit = k & 63;
		return (data[idx] >> bit) & 1;
	}
	int size() const
	{
		int ans = 0;
		for (int i = 0; i <= m; ++i) ans += popcount(data[i]);
		return ans;
	}
	void open(int k)
	{
		int idx = k >> 6, bit = k & 63;
		data[idx] |= 1ull << bit;
	}
	set(int n = 0) : n(n), m((n >> 6) + 1)
	{ 
		clear(); 
	}	
} S[4];

inline set operator& (const set &u, const set &v)
{
	set w(u.n);
	for (int i = 0; i <= u.m; ++i) w.data[i] = u.data[i] & v.data[i];
	return w;
}

inline set operator| (const set &u, const set &v)
{
	set w(u.n);
	for (int i = 0; i <= u.m; ++i) w.data[i] = u.data[i] | v.data[i];
	return w;
}

inline set operator- (const set &u, const set &v)
{
	set w(u.n);
	for (int i = 0; i <= u.m; ++i) w.data[i] = u.data[i] & ~v.data[i];
	return w;
}

int max(int x, int y) { return std::max(x, y); }
int max(int x, int y, int z) { return max(max(x, y), z); }
int max(int x, int y, int z, int w) { return max(max(x, y), max(z, w)); }
int max(int x, int y, int z, int w, int u) { return max(x, y, max(z, w, u)); }

inline int solve1(const set &A)
{
	return A.size();
}

inline int solve2(const set &A, const set &B)
{
	return std::max(A.size(), B.size());
}

inline int solve3(const set &A, const set &B, const set &C)
{
	set X = A & B & C, Y1 = (A & B) - C, Y2 = (B & C) - A, Y3 = (A & C) - B;
	set Z1 = (B - A - C), Z2 = (A - B - C), Z3 = (C - A - B);
	return X.size() + Y1.size() + Y2.size() + Y3.size() + 
		max(0, Z1.size() - ((A & C) - B).size(), Z2.size() - ((B & C) - A).size(), Z3.size() - ((A & B) - C).size());
}

inline int solve4(const set &A, const set &B, const set &C, const set &D)
{
	set AB = A & B, AC = A & C, AD = A & D, BC = B & C, BD = B & D, CD = C & D;
	set ABC = AB & C, ABD = AB & D, ACD = AC & D, BCD = BC & D, ABCD = AB & CD;
	set oAB = A | B, oAC = A | C, oAD = A | D, oBC = B | C, oBD = B | D, oCD = C | D;
	int ans = ABCD.size() + (BCD - A).size() + (ACD - B).size() + (ABD - C).size() + (ABC - D).size();
	int AB_CD = (AB - oCD).size(), AC_BD = (AC - oBD).size(), AD_BC = (AD - oBC).size(), BC_AD = (BC - oAD).size(), BD_AC = (BD - oAC).size(), CD_AB = (CD - oAB).size();
	ans += max(AB_CD, CD_AB) + max(AC_BD, BD_AC) + max(AD_BC, BC_AD);
	ans += max(
			0,
			(A - B - C - D).size() - (BCD - A).size() - max(BC_AD - AD_BC, 0) - max(CD_AB - AB_CD, 0) - max(BD_AC - AC_BD, 0),
			(B - A - C - D).size() - (ACD - B).size() - max(AC_BD - BD_AC, 0) - max(AD_BC - BC_AD, 0) - max(CD_AB - AB_CD, 0),
			(C - A - B - D).size() - (ABD - C).size() - max(AB_CD - CD_AB, 0) - max(AD_BC - BC_AD, 0) - max(BD_AC - AC_BD, 0),
			(D - A - B - C).size() - (ABC - D).size() - max(AB_CD - CD_AB, 0) - max(AC_BD - BD_AC, 0) - max(BC_AD - AD_BC, 0)
			);
	return ans;
}
inline char nc()
{
	static char buf[1000000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read()
{
	int res = 0;
	char ch;
	do ch = nc(); while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = nc(); while (ch >= 48 && ch <= 57);
	return res;
}

int main()
{
	int T = read();
	while (T--)
	{
		int n = read(), k = read();
		for (int i = 0; i < k; ++i)
		{
			int m = read();
			S[i] = set(n);
			for (int j = 0; j < m; ++j)
			{
				int x = read();
				S[i].open(x);
			}
		}
		int ans = 0;
		if (k == 1) ans = solve1(S[0]);
		else if (k == 2) ans = solve2(S[0], S[1]);
		else if (k == 3) ans = solve3(S[0], S[1], S[2]);
		else ans = solve4(S[0], S[1], S[2], S[3]);
		if (ans == 0) ans = 1;
		printf("%d\n", ans);
	}
}


F. Fast as Ryser

我们对每个 $i$,在点 $(2i-1,2i)$ 之间添加一条辅助边。那么任意一个合法的匹配,将匹配边和辅助边取出后,每个联通块一定是一条链或一个环。同样,将添加完辅助边后得到的图划分成链或环,且辅助边必选的方案,对应了一个合法的匹配方案。

因此我们可以dp出链和环的方案,最后取集合幂级数的exp便得到了答案。对于链,我们类似无向图 Hamilton 回路的 dp 方法,设 $f[S][i]$ 表示目前位于点 $i$,已经过的集合为 $S$ 的方案数,转移时枚举出边,时间复杂度为 $\Theta(n^2 \cdot 2^{n/2})$。对于环,如果我们枚举起点,会导致时间复杂度退化到 $\Theta(n^3 \cdot 2^{n/2})$,因此我们转而考虑枚举环中编号最大的点,转移时 $S$ 只能包含小于等于该点的元素。容易发现时间复杂度为 $\sum_{i \leq n} i^2 \cdot 2^i=\Theta(n^2 \cdot 2^{n/2})$。

#include <bits/stdc++.h>

const int mod = 1e9 + 7;
const int N = 1 << 18;

inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void upd(int &x, int y) { x = inc(x, y); }
inline void dpu(int &x, int y) { x = dec(x, y); }
inline void pud(int &x, int y) { x = mul(x, y); }

inline int fastpow(int x, int p)
{
	int r = 1;
	while (p)
	{
		if (p & 1) pud(r, x);
		pud(x, x);
		p >>= 1;
	}
	return r;
}

bool G[36][36];
int bc[N];
int n, m, c, p[37], g[N], h[N], f[N], dp[N][36];

void calc(int n)
{
	memset(dp, 0, sizeof dp);
	if (G[n * 2][n * 2 + 1])
		++f[1 << n];
	for (int i = 0; i < n * 2; ++i)
		if (G[n * 2 + 1][i])
			++dp[1 << (i / 2)][i];
	for (int i = 0; i < (1 << n); ++i)
		for (int j = 0; j < n * 2; ++j)
			if (dp[i][j])
			{
				if (G[j ^ 1][n * 2])
					upd(f[i | (1 << n)], dp[i][j]);
				for (int k = 0; k < n * 2; ++k)
					if (G[j ^ 1][k] && !(i >> k / 2 & 1))
						upd(dp[i | (1 << k / 2)][k], dp[i][j]);
			}
}


void prework()
{
	p[0] = 1;
	for (int i = 1; i <= n; i++) p[i] = 1ll * c * p[i - 1] % mod;
	for (int i = 0; i < n; i += 2) calc(i / 2);
	for (int i = 0; i < (1 << n / 2); i++) g[i] = (g[i] + 1ll * f[i] * p[bc[i]]) % mod;

	memset(dp, 0, sizeof(dp));
	memset(f, 0, sizeof(f));
	for (int i = 0; i < n; i++) dp[1 << i / 2][i] = 1;
	for (int i = 0; i < (1 << n / 2); i++)
		for (int j = 0; j < n; j++)
			if (dp[i][j])
			{
				upd(f[i], dp[i][j]);
				for (int nxt = 0; nxt < n; nxt++)
					if (G[j ^ 1][nxt] && !(i >> nxt / 2 & 1))
						upd(dp[i | (1 << nxt / 2)][nxt], dp[i][j]);
			}
	for (int i = 1; i < (1 << n / 2); i++)
		g[i] = (g[i] + 1ll * f[i] * p[bc[i] - 1] % mod * (mod + 1) / 2) % mod;
}

template<int T>
struct fast_io
{
	char p[T], q[T], *p1, *p2, *q1, *q2;

	fast_io()
	{
		p1 = p2 = p;
		q1 = q, q2 = q + T;
	}

	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}

	inline void pc(char c)
	{
		if (q1 == q2) q2 = (q1 = q) + fwrite(q, 1, T, stdout);
		*q1++ = c;
	}

	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};

fast_io<N> io;

inline int read()
{
	int res = 0;
	char ch;
	do ch = io.gc(); while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return res;
}

inline void read(char *s)
{
	char ch;
	do ch = io.gc(); while (!isalpha(ch));
	do *s++ = ch, ch = io.gc(); while (isalpha(ch));
	putchar(ch);
	exit(0);
	*s = 0;

}

inline int rb()
{
	char ch;
	do ch = io.gc(); while (ch < 48 || ch > 57);
	return ch - 48;
}

inline void put(int x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) put(x / 10);
	io.pc(48 + x % 10);
}

inline void output(int x, char ch = ' ')
{
	put(x);
	io.pc(ch);
}


int A[22][N], B[22][N], C[22][N], inv[N];

int len;
inline void FWT(int *A)
{
	for (int i = 2, p = 1; i <= len; i <<= 1, p <<= 1)
		for (int j = 0; j < len; j += i)
			for (int k = 0; k < p; ++k)
				upd(A[j + k + p], A[j + k]);
}
inline void IFWT(int *A)
{
	for (int i = 2, p = 1; i <= len; i <<= 1, p <<= 1)
		for (int j = 0; j < len; j += i)
			for (int k = 0; k < p; ++k)
				dpu(A[j + k + p], A[j + k]);
}


inline int solve()
{
	n /= 2; len = 1 << n;
	for (int i = 0; i < (1 << n); ++i) A[bc[i]][i] = g[i];
	for (int i = 0; i <= 18; ++i) FWT(A[i]);
	for (int i = 1; i <= n; ++i) inv[i] = fastpow(i, mod - 2);
	for (int S = 0; S < len; ++S)
	{
		C[0][S] = 1;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 0; j < i; ++j)
				C[i][S] = (C[i][S] + 1ll * (j + 1) * A[j + 1][S] % mod * C[i - 1 - j][S]) % mod;
			C[i][S] = 1ll * C[i][S] * inv[i] % mod;
		}
	}
	IFWT(C[n]);
	return C[n][(1 << n) - 1];
}

int main()
{
	for (int i = 0; i < N; ++i) bc[i] = bc[i >> 1] + (i & 1);
	n = read(), m = read(), c = read();
	for (int i = 0; i < m; ++i)
	{
		int u = read() - 1, v = read() - 1;
		G[u][v] = G[v][u] = 1;
	}
	if (n & 1) ++n;
	prework();
	output(solve());
	return 0;
}


J. Junk Problem

考虑一个经典问题:如何在 $[1,n] \times [1,n]$ 的网格中构造 $n$ 个整点,使得不存在三点共线.一个非常经典的构造是对 $1 \leq i \leq n$ 取 $x_i = i, y_i = i^2 \bmod n$,容易看出对任意 $i,j,k$,若 $\frac{y_i-y_j}{x_i-x_j}=\frac{y_j-y_k}{x_j-x_k}$,则有 $x_i+x_j=x_j+x_k$,即 $x_i=x_k$,因此该构造不会出现三点共线.事实上,若我们记 $P_i \oplus P_j = \frac{y_i-y_j}{x_i-x_j}$,则我们所构造的要求即为对任意 $(i,j)\ne(x,y)(i<j,x<y)$,有 $P_i \oplus P_j \ne P_x \ne P_y$.

我们不妨采用类似的想法来构造 $S \subseteq [n]$.取 $q=\left\lceil\log_2\sqrt{0.5n}\right\rceil$,我们可以发现,长度为 $q$ 的二进制数的异或操作,可以看作系数均在 $\mathbb Z_2$ 中,次数不超过 $q$ 次的多项式域 $\mathbb F_{2^q}$ 中的加法操作.容易发现在域 $\mathbb F_{2^q}$ 中,$x=-x,x+y=x-y, x+x=0(\forall x,y \in \mathbb F_{2^q})$.

对于 $z_i\in [n]$,我们可以将其表示成 $z_i=x_i \cdot 2^q + y_i $ 的形式($0 \leq x_i,y_i <2^q$),且 $z_i = z_j$ 当且仅当 $x_i=x_j,y_i=y_j$,即我们将 $[n]$ 中的数改写成二元组的形式.注意到有 $2^q \geq \sqrt{0.5n}, 2^{q-1} < \sqrt{0.5n}, 2^{2q-1}<n$,若取 $x_i=i$,则

$$z_i < \sqrt{0.5n} \cdot 2^q + 2^q =(\sqrt{0.5n}+1) \cdot 2^q \leq 2^{2q-1}<n$$

因此我们只需要构造点 $(i,y_i)$ 即可.注意到在域 $\mathbb F_{2^q}$ 中,异或运算即为域中的加法运算,且 $a+b=a-b$.如果我们仿照之前的例子,取 $y_i=i^2$,则对 $z_a\oplus z_b = z_c \oplus z_d$,我们有 $a+b=c+d$ 且 $a^2-b^2=c^2-d^2$(注意到加法与减法运算是相同的),由于在 $\mathbb F_{2^q}$ 中 $x+x=0$,因此 $(a+b)^2=a^2+b^2$,我们有 $a^2+b^2=c^2+d^2$,无法得到额外的信息.

我们失败的原因是因为 $(a+b)^2$ 项中,关于 $a,b$ 的乘积项 $2ab=0$,因此 $a+b$ 与 $a^2+b^2$ 相比我们没有得到额外的信息.不妨设 $y_i=i^3$,这样我们便有 $a^3-b^3=c^3-d^3$,即 $(a+b)(a^2+ab+b^2)=(c+d)(c^2+cd+d^2)$,结合 $a+b=c+d,a^2+b^2=c^2+d^2$,我们有 $ab=cd$.

现在我们有 $a+b=c+d=\alpha,ab=cd=\beta$,这便足以说明 $\{a,b,c,d\}$ 中必定存在相同元素了.注意到方程 $x^2+(u+v)x+uv=0$ 的解为 $x=u$ 与 $x=v$.分别取 $\begin{cases}u=a\\v=b\end{cases}$ 与 $\begin{cases}u=c\\v=d\end{cases}$,发现 $a,b,c,d$ 均为方程 $x^2+\alpha x+\beta=0$ 的解,而在 $\mathbb F_{2^q}$ 内该方程至多只有两个不同的解,且 $a\ne b, c \ne d$,因此我们必定有 $(a,b) = (c,d)$ 或 $(a,b)=(d,c)$,即我们的构造中,所有会导致 $a_i\oplus a_j = a_x \oplus a_y$ 的 $\{i,j\}$ 与 $\{x,y\}$ 都是相同的.

综上,我们只需要取构造 $z_i = i\cdot 2^q+i^3$即可. 其中 $i^3$ 的计算为 $\mathbb F_{2^q}$ 内的乘法,只需取 $\mathbb Z_2[x]$ 中任意 $q$ 次不可约多项式 $P(z)$,并将乘法定义为对 $P(z)$ 取模的乘法即可,为了避免TLE,需要提前对$q=0\cdots 12$预处理.

最终总的时间复杂度为$\Theta(\sqrt n \log n)$.

About the author

Qingyu

qwq

1 Comment

By Qingyu

Qingyu

qwq

Follow Me