[cdq分治+阈值优化+NTT]2022ICPC网络赛第一场 I【Permutation】题解
题目概述给出一个排列 $\{a_n\}$ ，对于这个排列的所有循环同构，求出排列的排名，对所有排名求和。解题报告对于一个固定的 $\{a_n\}$ ，根据康托展开，可以得到排名：$$
1+\su...
[分治+矩乘NTT]2022牛客暑期多校训练营（加赛）L【Lndjy and the mex】题解
题目概述Lndjy and the mex解题报告首先不难发现长度为 $len$ 的区间的方案数是相同的，因此只需要考虑区间长度而不需要考虑区间位置（乘 $n-len+1$ 即可）。然后考虑长度...
[链分治+分治NTT]LOJ6289【花朵】题解
题目概述LOJ6289解题报告这题显然是一个树形背包 $f_{x,j,0},f_{x,j,1}$ 表示 $x$ 没选 / 选了，子树里选了 $j$ 个的方案数。这个背包可以写成多项式形式，$B_...
[背包回退+二进制状压DP+NTT]2022牛客暑期多校训练营1 H【Fly】题解
题目概述Fly解题报告首先想到DP：$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位（从低位到高位），到 $i$ 这位时背包大小为 $j$ ，并且状态为 $0$ 小于 $1$ 相等 $...
[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解
题目概述Gambling Monster解题报告显然是个期望DP，倒着考虑正常一点（因为在 $n-1$ 处结束，步数为 $0$ ），所以我们倒着DP。定义 $f(i)$ 表示 $i$ 走到 ...
[FWT+高维前缀和]2020 ICPC 沈阳 M【United in Stormwind】题解
题目概述United in Stormwind解题报告太久没做过这种题了，其实非常套路。题目里给出了 $n$ 个 $01$ 串，把两个串异或就可以得到两个串不同位置的集合。首先我们可以利用FWT...
[容斥+生成函数+分治NTT]ACL Beginner Contest F【Heights and Pairs】题解
题目概述ACL Beginner Contest F解题报告直接求不太可做，我们考虑容斥，用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$ 个元素两两组合的方案数为 $f_...
[思维+组合+NTT]LOJ6261【一个人的高三楼】题解
题目概述给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。解题报告就是这题套个NTT，水博客真开心。可能略有卡常……示例程序#include<cstdio>...
[指数型生成函数+倍增+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\}$ 严格递增。解题报告不难转化成这...
