[分治+矩乘NTT]2022牛客暑期多校训练营（加赛）L【Lndjy and the mex】题解
题目概述Lndjy and the mex解题报告首先不难发现长度为 $len$ 的区间的方案数是相同的，因此只需要考虑区间长度而不需要考虑区间位置（乘 $n-len+1$ 即可）。然后考虑长度...
[容斥+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$ 。解题报告这可能是斯波题吧……除法分块然后每个...
