[分治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)$ ，这是假的完...
