当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

分类 题解 下的文章

给定 n 和长度为 n 的数组 \{a_i \} _{i=1}^n ,求满足 \forall i \in [1, n], c_i | b_i, b_i | a_i 并且 \prod_{i=1}^n c_i^2 \leq \prod_{i=1}^n b_i\{b_i\}_{i=1}^n\{c_i\}_{i=1}^n 的方案数。

n \leq 100,\ a_i \leq 10^9

READ MORE

傻逼题,CF 的数据是假的,不开 std::multiset 都可以过。

发现我们直接缩成一棵广义圆方树然后进行维护。修改点权的时候如果我们暴力修改圆点周围的方点显然可能挂掉,但是如果我们的方点只存圆方树上孩子的信息,那么就只用更新 O(1) 次了,这样的话在求 u \rightarrow v 的路径的时候判断一下 LCA 是不是方点即可。时间复杂度 O(n \log^2 n)

READ MORE

定义 s(x, y) 为将 xy 进行不进位加法的结果,求对于 a_{1 \dots n} 依次选出 n 个可以重复的数 b_{1 \dots n} ,求 \forall i \in [1, n] , s(b_1, b_2, b_3, \dots b_n) = i 的方案数目。n, a_i \leq 10^5 ,对 2^{58} 取模。

READ MORE

首先我们需要理解普通的 FWT 即给一个向量左乘一个矩阵进行转移,这在 k 进制下同样适用。用 w(i,j) 表示 \operatorname{fwt} 矩阵的第 i 行第 j 项。

对于给定的两个数列 ABC 是他们 k 进制下异或卷积的结果,即

\sum_{i \oplus j = k} A_i \times B_j = C_k

显然 FWT 还需要我们满足一个性质,即

\begin{aligned} \operatorname{fwt}(A)[x] \times \operatorname{fwt}(B)[x] &= \operatorname{fwt}(C)[x] \\ \sum_{i=0}^n w(x, i) A_i \sum_{j=0}^n w(x, j) B_j &= \sum_{k=0}^n w(x, k) C_k \end{aligned}

为了方便计算,我们希望能够构造出这样的 w 使得

\sum_{i \oplus j = k} w(x, i) A_i \times w(x, j) B_j = w(x, k) C_k

如果有

\forall i \oplus j = k, w(x, i) \times w(x, j) = w(x, k)

显然这就是个合法的 k 进制 \operatorname{fwt} 变换。

我们只构造一个满足 \forall i \oplus j = k, w(x, i) \times w(x, j) = w(x, k) 的矩阵 T 即可。

READ MORE

对于一个 1 \cdots n (n \leq 5 \times 10^5) 的排列 p_{1 \cdots n} ,定义 next_i 为第一个 j 满足 i < j, p_i < p_j ,如果不存在这样的 j ,则 next_i = n + 1 。给定一个缺失若干位的 next 数组,求构造任一合法的 p 数组。

READ MORE