XX Open Cup, Grand Prix of Zhejiang
The problemset is just gorgeous.
Contest Links: Yandex, Baekjoon, QOJ
Results: ptz-camp, opentrains
A. Alternative Accounts
直接容斥即可. 比较无脑的做法就是直接 bitset.
#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;
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)
{
data = new uint64_t[m + 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);
}
}
B. Bitset Master
WIP
C. Cyclic Distance
WIP
D. Data Structure Quiz
Unsolved
E. Evil Sequence
Unsolved
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;
}
G. Geometry PTSD
Unsolved
H. Heavy Stones
WIP
I. Interesting Game
WIP
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)$.
K. Knowledge-Oriented Problem
WIP
L. LCM Sum
WIP