「Codeforces 653G」Move by Prime – 题解

主要思路

这些 3000+ 题目里做过最小清新的。

首先肯定可以想到,分解质因子之后,对于一个 \(p^c\),把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。

继续阅读「Codeforces 653G」Move by Prime – 题解

「Codeforces 666C」Codeword – 题解

主要思路

就这?思博题。

总觉得做过啊。答案很显然跟字符无关,我们需要固定最左边的子序列,然后枚举最后一位,得出结论(子序列 \(T\)、目标串长 \(n\)):

\[ ans = \sum_{i = |T|}^n 25^{i – |T|} \times 26^{n – i} {i – 1 \choose k – 1} \]

考虑把 \(n\) 提出来:

\[ ans = 26^n \sum_{i = |T|}^n 25^{i – |T|} \times 26^{-i} {i – 1 \choose k – 1} \]

发现一个重要性质:\(\sum |T| \leq 10^5\),所以对于不同的 \(|T|\),最好情况下个数为 \(\Theta(\sqrt{n})\)。那么既然 \(n\) 可以被独立出来,那么最后复杂度就是 \(\Theta(|T|\sqrt{n})\)。

继续阅读「Codeforces 666C」Codeword – 题解

BZOJ3162:独钓寒江雪 – 题解

主要思路

刚看这题我人都是懵的…仔细看了看能大概想到,定一个根然后做 DP 得到方案,然后对于相同形态的子树进行方案分配即可。(但是不会写)

具体而言,转换成有根树的方法就是用重心来做根(如果有两个重心的话,就加一个虚根),并且每次 DFS 完之后用 Hash 值排序,然后进行分组转移。

转移的时候,可以给每一种情况进行标号,然后用前缀的组合意义来做转移即可。具体:\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。

如果加了虚点,那就判一下就好了。

继续阅读BZOJ3162:独钓寒江雪 – 题解

[Fortuna OJ]Aug 13th – Group A 解题报告

A – Count

真难。

简单来讲,题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\),然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)(注意,\(A\)并没有被整体取模,只是各项余数之和),可知\(A \mod m = n \mod m\),且\(A\)的上限就是\(A = k(m – 1)\)(各项上限)。

我们做了这样一个设置之后,问题就可以转换为:对于每一个不同的\(A\),满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先,我们可以先枚举每一个\(A\)来缩小问题的范围,根据\(A\)所满足的条件,可以这样遍历\(i\)来获得每一个\(A\):

继续阅读[Fortuna OJ]Aug 13th – Group A 解题报告

BZOJ4361:isn 题解

解法

这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数,方程为:

\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]

发现可以用树状数组优化,所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\),考虑对答案的贡献。对于一个\(i\),有\(g[i] * (n – i)!\)种方案做变换,但是考虑这\((n – i)!\)中包含了提前变换完成的可能,也就是在我们从合法序列中删去了合法元素的可能,这样肯定是不行的。考虑进行容斥,贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\),表示在这些里选择\(i+1\)个合法元素的方案。

继续阅读BZOJ4361:isn 题解

Codeforces Round #539 (Div. 2) 解题报告 (CF1113)

C – Sasha and a Bit of Relax

其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\),然而这个运算可以直接移项:因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数,我们只需要在 Trie 树末端维护奇偶计数即可。

继续阅读Codeforces Round #539 (Div. 2) 解题报告 (CF1113)