P5517 [MtOI2019]幻想乡数学竞赛
闲扯数列练习好题。
题面P5517 [MtOI2019]幻想乡数学竞赛
Solution直接暴力矩阵乘法肯定不行，复杂度爆了。
考虑简化，可以发现这个式子很有规律。
由高一的数列知识，我们做出如下操作：
a_n=3\cdot a_{n-1}+a_{n-2}-3\cdot a_{n-3}+3^n\\
...
test20191216
发表于
闲扯我觉得我可以直接入土了。。。
$T1$ 题面看错，数据范围看漏，直接爆零。。
题面[2020WC集训训练赛day2]
$T1$Solution我们设 $f_{u,k}$ 表示从 $fa_u$ 到 $1$ 这条链上，合法的 $1\sim k$ 的序列个数；设 $g_{u,k}$ 表示 $u$ 的子
...
P5395 【模板】第二类斯特林数·行
发表于
闲扯多项式乘法练习题
题面P5395 【模板】第二类斯特林数·行
Solution我们设 $s_{n,m}=\begin{Bmatrix} n\\ m\end{Bmatrix}$ 。
考虑第二类斯特林数的通项式：
s_{n,m}=\sum_{i=0}^m (-1)^iC_{m}^i\frac{(m
...
Codeforces Round 608 Div. 2
发表于
闲扯今天的题太坑了， $B$ 题 $fst$ 了一堆（包括我），果然还是太捞了。
也可以到我 $Luogu$ 博客上康康 $B\sim D$ 的题解（也许会具体点？？）。
题面Codeforces Round #608 (Div. 2)
$A$可以发现只有 $jecket$ 是共有的，直接枚举两种分
...
2707. [SDOI2012]走迷宫
发表于
闲扯概率期望好题。
题面#2707. [SDOI2012]走迷宫
Solution设 $E(u)$ 表示从 $u$ 出发，到达 $t$ 的期望步数。
显然，我们有 $E(u)=\sum_{(u,v)\in E}\frac{E(v)+1}{deg_u}$ 。
对于不同 $SCC$ 里面的点，我们显然可
...
P3232 [HNOI2013]游走
发表于
闲扯期望问题经典题。
题面P3232 [HNOI2013]游走
Solution对于每一条边，我们经过它时有两种情况：
从 $u$ 点出发，经过的概率为 $\frac{1}{deg_u}$ 。
从 $v$ 点出发，经过的概率为 $\frac{1}{deg_v}$ 。
我们设 $E(u)$ 表示点
...
P3241 [HNOI2015]开店
发表于
闲扯动态点分治的常数是真的大。。。
题面P3241 [HNOI2015]开店
Solution这道题有两种思路：
树链剖分+动态开店点线段树先写出答案要求的式子：
ans_u=\sum_{i=1,L\leq col_i\leq R}^n dist_{u,i}\\
=\sum_{\cdots}dis
...
P3345 [ZJOI2015]幻想乡战略游戏
发表于
闲扯感觉这题基本就是看的题解，不过还是大概对动态点分治有了些了解吧，决定还是写篇题解记录一下。
题面P3345 [ZJOI2015]幻想乡战略游戏
Solution先考虑给出每个点的军队个数怎么办。
我们考虑通过换根 $DP$ 的方式来求解。
具体的，我们设 $sz_u$ 表示 $u$ 的子树中军队
...
CF1265E Beautiful Mirrors
发表于
闲扯期望经典模型？
题面CF1265E Beautiful Mirrors
Solution我们设 $E(i)$ 表示询问当前在询问第 $i$ 面镜子，离终止的期望天数，那么答案就是 $E(1)$ 。
我们将终止条件转化为问到第 $n+1$ 面镜子，无论回答是什么都结束。那么我们有 $E(n+1)=
...