ZigZagK的博客
[生成函数+多项式除法求系数]2021牛客暑期多校训练营8 H【Scholomance Academy】题解
题目概述Scholomance Academy解题报告伪装成数论题的多项式全家桶题。首先我们可以把 $\varphi(n)$ 拆成 $\prod\varphi(p_i^{a_i})$ ,因此不难...
[线性代数+多项式取模]洛谷4723【常系数齐次线性递推】题解
题目概述给出递推 $f$ 的 $[0,K-1]$ 项,给出系数 $\{a_K\}$ ,$f_n=\sum_{i=1}^{K}a_if_{n-i}(n\ge K)$ ,求第 $n$ 项。$n\le...
[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解
题目概述HDU7057解题报告首先这道题很显然可以用生成函数做,但是 $n$​ 太大了,因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$​​ 表示花费 $i$​​ 时的生成函数,那么不...
[差分+二分+主席树]2021牛客暑期多校训练营7 K【xay loves sequence】题解
题目概述xay loves sequence解题报告先对数组差分,令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+1$ 和 $-1$ ,所以不难发现...
[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解
题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题,定义 $Find(p,l,r,i)$​​​ 表示在 $[l,r]$​​​ 的节点 $p$​​​ 前...
[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解
题目概述Gambling Monster解题报告显然是个期望DP,倒着考虑正常一点(因为在 $n-1$ 处结束,步数为 $0$ ),所以我们倒着DP。定义 $f(i)$​ 表示 $i$​ 走到 ...
[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
题目概述Starch Cat解题报告正解是猫树,但是我不会,所以我选择黑科技。首先我们能想到一个比较暴力的做法,每次询问 $x,y$ 路径上的最大独立集,就是求 $x\to LCA(x,y),y...
[二进制分块]2021牛客暑期多校训练营3 I【Kuriyama Mirai and Exclusive Or】题解
题目概述Kuriyama Mirai and Exclusive Or解题报告第一种操作没什么好讲的,我们关注第二种。这种加法和异或混合的一般都只能考虑按位统计贡献。考虑 $[L,R]$ 第 $...
[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解
题目概述Prof. Pang's sequence解题报告首先根据经典套路,我们记录 $pre_i$ 表示 $i$ 上次的出现位置,这样的话对于一个左端点 $L$ ,只有 $pre_i<L...
[FWT+高维前缀和]2020 ICPC 沈阳 M【United in Stormwind】题解
题目概述United in Stormwind解题报告太久没做过这种题了,其实非常套路。题目里给出了 $n$ 个 $01$ 串,把两个串异或就可以得到两个串不同位置的集合。首先我们可以利用FWT...