April 26, 2020

给定 nn 个整数 a1,a2...an\langle a_1, a_2 ... a_n \rangle,在 [0;2m)[0; 2^m) 的范围内。对于 k[0;m]k \in [0; m],求选出一个子集使得异或和的二进制表示有 kk11 的方案数。

1n2×105, 0m531 \leq n \leq 2 \times 10^5,\ 0 \leq m \leq 53

April 23, 2020

定义两个简单无向图 G1=(V1,E1),G2=(V2,E2)G_{1} =( V_{1} , E_{1}) , G_{2} =( V_{2} , E_{2}) 的乘积为一个新的图 G1×G2=(V,E)G_{1} \times G_{2} =\left( V^{\star} , E^{\star} \right),其中 V={(a,b)aV1,bV2}\displaystyle{V^{\star} = \left\{ {(a, b)| a \in V_{1}, b \in V_{2} }\right\}}E={((u1,v1),(u2,v2))(u1,u2)E1,(v1,v2)E2}\displaystyle{E^{\star} =\left\{\left(( u_{1} , v_{1}) , ( u_{2} , v_{2})\right) \mid ( u_{1} , u_{2}) \in E_{1}, ( v_{1} , v_{2}) \in E_{2}\right\}}

对于正整数 nn ,以及给定的图 G1,G2,,GnG_{1} , G_{2} , \dotsc , G_{n} ,我们令 H=(((G1×G2)×G3)×)×Gn\displaystyle{H = (((G_1 \times G_2) \times G_3) \times \cdots) \times G_n}。若每个 GkG_k 中每任意两点都有 12\frac12 的概率有边,求 HH 的连通块个数的期望。

答案对 998244353998244353 取模。

1n,mk1051\le n, m_k\le 10^5

March 27, 2020

给定 nn 次多项式

f(x)=i=0naixif(x) = \sum_{i=0}^n a_i x^i

QQ 次询问,第 ii 次询问 f(qi)f(q_i)998244353998244353 取模的值。

其中 qiq_i 是一个一阶线性递推,给定 q0,x,yq_0, x, y ,满足

qn=xqn1+yq_n = x q_{n-1} + y

1n2.5×105, 1Q106, 2x<998244353, 0q0,y<9982443531 \leq n \leq 2.5 \times 10^5, \ 1 \leq Q \leq 10^6, \ 2 \leq x < 998244353, \ 0 \leq q_0, y < 998244353

September 27, 2019

本文以矩阵交相关内容为主,忽略掉了大部分证明,感兴趣的读者请自行阅读集训队论文。

拟阵的定义

M=(S,L)M = (S, L) 表示一个定义在有限集 SS 上,独立集的集合为 LL 的拟阵。其中 LLSS 的一些子集构成的集合。拟阵 MM 满足以下公理:

  • (遗传性). 如果 IL,JII \in L, J \subseteq I,那么 JLJ \in L
  • (交换性). 如果 I,JLI,J \in LI<J|I| < |J|,那么 xJI\exists x \in J \setminus I 满足 I{x}LI \cup \{x\} \in L

如果 ILI \in L,我们称 II 是独立的,也称 II 是独立集;否则,我们称 II 是不独立的,也成 II 是非独立集。通常,我们认为 \varnothing 是独立的。

July 20, 2019

给定 nn{ai}\{a_i\},满足 a0a1an10a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0,求出在 nn 维空间中从 (0,0,,0)(0, 0, \ldots, 0) 走到 (a0,a1,,an1)(a_0, a_1, \ldots, a_{n - 1}),每一步使某一维坐标增加 11 的方案中随机选出一种,满足经过的所有点 (x0,x1,,xn1)(x_0, x_1, \ldots, x_{n - 1}) 都满足 x0x1xn1x_0 \geq x_1 \geq \cdots \geq x_{n - 1} 的概率,答案模 10045358091004535809 输出。

n,ai5×105n, a_i \leq 5\times 10^5