ZigZagK的博客
[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(1)1010【Walk】题解
题目概述HDU7147解题报告从来没做过这种容斥,长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和,以及 $g_i$ 表示走了 $i$ 行全非法的权值和(特殊的,如果 $i=1$...
[矩阵乘法+线段树]Codeforces1701F【Points】题解
题目概述CF1701F解题报告对于 $x$ ,设 $[x-d,x-1]$ 上共有 $cnt$ 个点,那么以 $x$ 作为结尾的三元组个数为 ${cnt\choose 2}={1\over 2}(...
[矩阵乘法+线段树]The 2021 ICPC Asia Nanjing Regional Contest E【Paimon Segment Tree】题解
题目概述Paimon Segment Tree解题报告首先肯定考虑离线,把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[0,x-1])$ 。然后我们按顺序...
[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
题目概述Starch Cat解题报告正解是猫树,但是我不会,所以我选择黑科技。首先我们能想到一个比较暴力的做法,每次询问 $x,y$ 路径上的最大独立集,就是求 $x\to LCA(x,y),y...
[线段树+矩阵快速幂]Codeforces446C【DZY Loves Fibonacci Numbers】题解
题目概述有两种操作:1.将 $a_i,i\in[L,R]$ 加上 $fib_{i-L+1}$ 。2.求 $\sum_{i=L}^{R}a_i$ 。解题报告水Blog.jpg。先把原序列改成 $0...
[原根+循环矩阵快速幂]liu_runda NOIP模拟题【随】题解
解题报告先来介绍一波原根:如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ,那么 $g$ 是 $P$ 的一个原根,如果 $P$ 是素数那么一定有...
[矩阵快速幂]BZOJ4870(Shoi2017)【组合数问题】题解
题目概述求 $\sum_{i=0}^{+\infty}{nk\choose ik+r}$ 。解题报告我好斯波啊……这个式子很明显不可算,应该考虑实际意义,发现就是在 $nk$ 个里选出 $mod...
[除法分块+矩阵快速幂]HDU6395【Sequence】题解
题目概述$f_1=A,f_2=B,f_n=Cf_{n-2}+Df_{n-1}+\lfloor{P\over n}\rfloor$ ,求 $f_n$ 。解题报告这可能是斯波题吧……除法分块然后每个...
[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解
题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ,有 $m$ 个询问,每次询问先交换 $P_x,P_y$ ,然后询问 $max\...