莫名其妙的混了一个上午 卷 众所周知，集训队作业一下发，队员们立刻开始了卷卷卷的日子。 qjd 作为国家队的候选人之一，当然要争当卷王。于是他把这一堆集训队作业摆成了一个树状结构，第一天他就打算做一大批集训队作业题。 然而如果做的两个集训队作业题在树上有直接连边（即在树上相邻），那么 qjd 就会感觉非常不爽从而出 \(114514\) 个多项式毒瘤题扔给大家做。 小 w 非常不希望这样的事情

题目 小七养了很多头猪，它们分布在 \(n\) 行 \(m\) 列中，其中第 \(i\) 行第 \(j\) 列的猪圈养的是第 \(w_{i,j}\) 种猪。 小七有时会选择一个子矩形范围内的猪圈进行巡视，如果该子矩形包含 $i $行 $j $列 \((1 ≤ i ≤ n, 1 ≤ j ≤ m)\)，且子矩形内含有的猪种类编号最大值减去编号最小值恰好为 \(i × j-1\) ，则小七会获得 \(i

题目 小七擅长泰拳，某天他打算与小枣切磋拳技，一共需要进行 \(n\) 次比赛。 由于双方拳技难分上下，每场比赛小七获胜或落败的概率都是 \(\dfrac{1}{p+2}\) ，平局 的概率是 \(\dfrac{p}{p+2}\) 。 若最后小七获胜场数大于落败场次，且平局次数为$ k$ ，则能获得 \(k + 1\) 奖励分。 小七想知道，他能获得的奖励分的期望是多少呢？为了避免精度误差，你需

「HAOI2018」奇怪的背包 其实这题和背包一点关系都没有。 题目要求解方程的解数， \[\sum x-ia-i\equiv w\pmod p\] 根据裴蜀定理，方程有解当且仅当\(\gcd(a-1,a-2,\cdots,a-n,p)\mid w\) 于是设\(f[i][j]\)表示前\(i\)个数的与\(p\)的最大公约数是\(j\)时的方案数，转移只需要枚举当前这个选不选，不需要考虑具体

题号是\(\text{51nod}\) 1383和1048 \(n\le 10^6\) 这档分\(O(n\log n)\)或者\(O(n)\)都可以。 \(\log\)的是用\(2\)的幂跑一次完全背包 线性的考虑每个数从为空的序列开始是通过\(+1\)或者集体\(\times 2\)得到的。 \(f[i]=(i\&1)?0:f[i/2]+f[i-1]\) \(n\le 10^{30}\)

Amount of Degrees 这篇博客是来贴代码的，真正的题解看这里 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <bits/stdc++.h>using namespace std;const int N = 32;int f[N][N],

题目链接 题目 给定一颗 \(n\) 个点的树。每个点都一个正整数点权 \(Ai\) ，你需要支持以下两种操作： 1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点（包括点 \(x\) 和点 \(y\) ）的点权是否构成一个从 \(1\) 开始的排列（即若这条链长度为 \(len\) ，那么问点权集合是否为 \({1,2,⋯,len}\) ）。 2、将 \(Ax\) 修改为 \(y

长城之旅 或许是全网第一篇能看的题解 (?) 首先\(\text{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}\) 根据定义可以证明。 关于\(\gcd\)的一个结论。 \(\gcd(k^{2^l}+1,k^{2^r}+1)=(k\& 1)?2:1\ ,r>l\) 分类讨论一下 1. \(k\%2=0\)时，假设\(k^{2^l}+1\)有约数\(d

题目 有Q个查询，对于每一个查询q[i]，请计算S(q[i])%m。 拆一下第二个函数 \[S((\lfloor\frac{n}{k}\rfloor-1)*k+i)=S((n-k)-n\%k+i)\] 可以发现这个式子按\(\mod k\)余数分类后，可以用矩阵乘法来做。 以下来自题解 可以先把数据分块，每K个一块，后一块和前一块之间的关系可以用矩阵来表示。 这个矩阵太大了。直接做矩阵乘法

备忘录 & 任务列表 小技巧 逆元 线性筛\(1-p\)逆元 设\(t=\lfloor P /i\rfloor\)，\(k=P\%i\) \(t*i+k\equiv 0 \pmod {P}\) \(-t*i\equiv k \pmod {P}\) \(-t*inv[k]\equiv inv[i]\pmod {P}\) 带回\(t,k\) 1inv[i]=(P-P/i)*inv[P%i]%P