ZigZagK的博客
[分治NTT+倍增]2022 CCPC 桂林 D【Alice's Dolls】题解
题目概述Alice's Dolls解题报告定义 $f_{n,k}$ 表示要得到 $n$ 个物品,$x^k$ 的期望。$n>1$ 的情况十分复杂,但是根据期望的线性性,$n>1$ 的情...
[离线+Trie+倍增]2022牛客暑期多校训练营2 F【NIO with String Game】题解
题目概述NIO with String Game解题报告感觉赛时榜都歪飞了……这题明明不难却只有20个队过。由于对 $t_i$ 只有单字符加的操作,因此最终所有 $t_i$ 长度和不会很长,可以...
[AC自动机+倍增]The 2021 China Collegiate Programming Contest (Harbin) L【Karshilov's Matching Problem】
题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机,在 $fail$ 树上求和就可以得知匹配到 $p$ 点时的权值和。然后我们观...
[思维+二分+ST表]2020-2021 ACM-ICPC Brazil Subregional Programming Contest M【Machine Gun】题解
题目概述CF GYM 102861M解题报告首先要仔细读题,题目保证了覆盖的点的个数总和不超过 $10^6$ ,因此只需要想办法快速找到被覆盖的点就行了。如果按照题目里的说法很难快速查找,因此我...
[思维+构造+倍增+exgcd]Codeforces1427E【Xum】题解
题目概述CF1427E解题报告神仙构造题,我又来翻译题解啦QAQ!如果 $(x,y)=1$ ,根据裴蜀定理,一定能求出两个正整数 $a$ 和 $b$ 使得 $ax-by=1$ ,而且如果 $ax...
[倍增]Codeforces1408F【Two Different】题解
题目概述CF1408F解题报告我们可以把 $2$ 个不同的变成相同的,$4$ 个不同的先变成 $2$ 个不同的,再变成相同的。以此类推,$2^k$ 个不同的可以变成相同的,需要的次数是 $O(2...
[思维+倍增]ACL Contest 1D【Keep Distances】题解
题目概述ACL Contest 1D解题报告根本不会做,我来翻译原题解了QAQ。如果要求的是 $[L,R]$ 中最长的good set,我们直接 从 $L$ 开始向后贪心 或者 从 $R$ 开始...
[指数型生成函数+倍增+NTT]BZOJ5381【or】题解
题目概述求多少序列 $\{A_n\},A_i\in[1,2^K)$ 满足 $B_1=A_1,B_i=B_{i-1}\ or\ A_i$ 的序列 $\{B_n\}$ 严格递增。解题报告不难转化成这...
[第一类斯特林数+倍增+NTT]Codeforces960G【Bandit Blues】题解
题目概述求有多少 $n$ 的排列满足从左边会更新 $A$ 次最大值,从右边会更新 $B$ 次最大值。解题报告第一类斯特林数:$s(n,k)$ 表示把 $n$ 个数分成 $k$ 个圆排列的方案数。...
[倍增+线性基]BZOJ4568(Scoi2016)【幸运数字】题解
题目概述给出一棵树,求从 $x$ 到 $y$ ,经过的每个点都可以决定异或还是不异或,求能够得到的最大异或值。解题报告倍增+线性基就好啦,复杂度为 $O(60^2nlog_2n)$ ,这是假的完...