矩阵树定理用于计算无向图生成树个数，和基尔霍夫矩阵的行列式密切相关。 Part 1 前置知识 $\text{Kirchhoff}$ 矩阵 我们记 $K$ 为 $\text{Kirchhoff}$ 矩阵，并计算出无向图$G$的度数矩阵 $D$ 和邻接矩阵 $A$ ，那么我们同通过 $K=D-A$ 就 ...

维护全局标记 $(a,b)$ 表示维护的数 $x$ 的实际值为 $ax+b$ ，这里需要始终保证 $a≠0$，初始时 $a=1,b=0$。 单点修改成 $val$ 就把维护的值改成 $\frac{val - b}{a}$。注意需要逆元需要实时维护。 加法直接加。 乘法若 $val≠0$ 就直接乘，注 ...

2019.9.9 P4462 [CQOI2018]异或序列 口胡一下。 开个桶记录异或值，然后就可做了。 代码先坑着，还没写完。 upd on 2019.9.10 22:09 代码写完了，cmp写错了调了好久 代码 2019.9.10 校内训练20190910 T1 旅馆 大原题+sb题 将$1$ ...

分类讨论 $1.$不进行翻倍操作 我们可以发现$[\lceil\frac{a[i]}{2}\rceil,a[i])$这个区间的数不会翻倍，其他部分随便选,假设有$x$个。 所以$ans=\displaystyle\binom{n-x-1}{k}$ $2.$进行翻倍操作 我们可以发现$[a[i],2a ...

$40$分乱搞，$DP$ $100$分法$1$ 我们可以用$40$分的做法打一张表，然后找找规律就发现$ans=C^{A+1}{A+B-2} *S^{A+B-2}{n-1}$了。 啥？你说你不会$Stirling$数？ 出门左转具体数学，包教包会 法$2$ 我们理性分析一下 我们可以先挑出最高的位置 ...

题目链接 求值： $\displaystyle\sum_{i=x}^{n}\sum_{j=y}^{m}[\gcd(i,j)=k]\qquad(1\leqslant T,x,y,n,m,k\leqslant 50000)$ 分析由容斥原理可将原式分成4块处理，每一块式子为 $\displaystyle ...

阶梯$Nim$ 对于这种游戏，必胜策略就是只要你把x颗石子从偶数层拿到奇数层，那我就把这x颗石子拿到偶数层。 若我们从$i$处取走了$x$个石子，那么下一次及以后就可以在$i+1$处多取$x$个，相当于把$i$处的$x$个石子加到了$i+1$处 ，所以可以转化成阶梯$Nim$ 不懂可以看一下http ...

分析先二分答案转化成一个判定性问题，这样记录就没有先后之分了。 然后考虑什么情况会出现矛盾 两条记录是同一时刻的，但人数不同。 解决：直接特判 举个例子 小$A$在$x$时刻写过一个记录，又在$y$时刻写了一个记录，小$B$写除了他没有人了。 解决：对每个人记录一下最晚开始时间和最早结束时间 ...

因为LATEX挂了，所以重新交一遍 分析 我们设原向量为$(a_1, b_1)$,$(a_2, b_2)$。设新向量为$(a_3, b_3)$，$(0, a_4)$ $\therefore$ $a_3=gcd(a_1,a_2)$ $\therefore$ $a_1x + a_2y = a_3$ $\ ...

看到好像没人发树状数组的题解，于是就发一篇 题目大意给出一个长度为$n$的序列$a$,给出$m$个查询$l$,对于每个查询输出$[l,n]$的区间内不同数的个数。 分析： 将查询按照$l$的大小排序，从大到小的遍历，每次将$>=$当前$l$的位置的$a[i]$全部加入树状数组，让树状数组记录每 ...