[UOI 2021] 哥萨克与 GCD
模拟赛遇到的，做法非常有启发，但如果见过能很快秒的类型。
让我们先从怎么才能唯一确定一个bbb数组来考虑，记Si=∑j=1ibjS_i = \sum_{j=1}^{i} {b_j}Si =∑j=1i bj ，我们询问一段区间的和，也就相当于询问了Sr−Sl−1S_r - S_{l-1}Sr −Sl−1 的值，而要确定bbb则要∀i\forall {i}∀i，SiS_iSi 都是确定的。
这样我们可以做一个转化，每次询问相当于l−1l-1l−1和rrr点连一条边，最后使得nnn个点是连通的。到这我们可以写一个非常暴力的MSTMSTMST拿到前两个点的分。
进一步思考。从gcdgcdgcd本身性质看，对于任意一个序列的前缀gcdgcdgcd一定是单调不增的（显然好证明）。这样在询问的过程中一定是中间的点连向111或者nnn点，显然最优。
怎么计算答案呢？考虑一个简单贪心，既然每个点要不连向111或者nnn，贪心取一个代价最小的连显然是对的。
记Li=gcdj=1iajL_i = \gcd_{j=1}^{i} {a_j}Li =gcdj=1i aj ，Ri=gcdj=inajR_i = \gcd_{j=i}^{n} {a_j}Ri =gcdj=in aj ，
Ans=∑i=2n−1min(Li,Ri)+gcdi=1naiAns = \sum_{i=2}^{n-1} {min(L_i,R_i)} + \gcd_{i=1}^{n} {a_i}Ans=∑i=2n−1 min(Li ,Ri )+gcdi=1n ai 显然最后需要nnn连向111有一个全局gcdgcdgcd。
现在再考虑带修，对于单点修改，我们考虑可以用线段树维护这个东西（或许在我的做法中树状数组也可以？你们可以试一试）。每个线段树节点维护一个当前区间的gcdgcdgcd和当前区间中每一段不同的gcdgcdgcd值和对应的长度。
为什么这样看似暴力是对的？这就涉及到一个重要性质（或许后面考虑gcdgcdgcd问题就遇到了呢？）：每次前缀gcdgcdgcd改变时，值一定至少缩小一半！，所以在这题中不同的gcdgcdgcd值在线段树节点存的必然不大于log(109)≈30\log (10^9) \approx 30log(109)≈30。当然pushuppushuppushup也是好做的相同的合并，不同的加入。
统计答案时用双指针同时处理LLL和RRR即可，记得处理LLL和RRR边界，因为是∑i=2n−1\sum_{i=2}^{n-1}∑i=2n−1 。
这样我们就做完了一道紫题。
P14943 浅谈矩阵乘法
一道图论建模的好题。
题意是对于一个n×nn \times nn×n方阵AAA，是否∀i,j∈[1,n]\forall {i,j \in [1,n]}∀i,j∈[1,n]且kkk为任意非负整数，(Ak)i,j(A^k)_{i,j}(Ak)i,j 有上限？
如果我们考虑把矩阵抽象成一个图，Ai,jA_{i,j}Ai,j 表示iii到jjj有一条长为Ai,jA_{i,j}Ai,j 的有向边，而(Ak)i,j(A^k)_{i,j}(Ak)i,j 表示的是从iii到jjj恰好走kkk步的距离，考虑到kkk理论上是一个+∞+\infty+∞的值，所以我们要判断无论从iii到jjj走多少步答案不是+∞+\infty+∞。
反向考虑什么时候会达到+∞+\infty+∞？考虑到任意两点iii和jjj对答案有影响，当且仅当i,ji,ji,j在一个sccsccscc内或者有路径到达，所以我们有三种情况：
1.sccsccscc内权值和 >1>1>1，显然在kkk足够大时，答案达到+∞+\infty+∞。
2.sccsccscc不是一个简单环，多个环相交错，导致形成指数级路径个数，从而答案达到+∞+\infty+∞。
3.多个满足上面条件的sccsccscc相连，导致多个sccsccscc分配步数呈线性或者多项式级增长。
前两个条件用tarjantarjantarjan处理即可，3的话用缩点建DAGDAGDAG跑拓扑+dpdpdp即可。
应该会有更好的实现吧（赛时做时实现的没用到tarjantarjantarjan但思路一样的）。
这里给出这种做法的代码。
转圈
神秘数论题，感觉比较简单。
刚刚开始看没思路，但我们可以先用草稿纸手推一下前几次操作：
1→(m+1)→(m+1)+(m+1)m=(m+1)2→(m+1)3......1 \to (m+1) \to (m+1)+(m+1)m=(m+1)^2 \to (m+1)^3......1→(m+1)→(m+1)+(m+1)m=(m+1)2→(m+1)3......（当然要模nnn）
wow！！原来是这样，我们要求的就是：
满足(m+1)k≡1(m+1)^k \equiv 1(m+1)k≡1 (mod(mod(mod n)n)n)，的最小正整数kkk。
然后我们发现nnn为质数，所以ϕ(n)=n−1\phi {(n)}=n-1ϕ(n)=n−1且gcd(m+1,n)=1gcd(m+1,n)=1gcd(m+1,n)=1（要特判m=n−1m=n-1m=n−1）。
由欧拉定理得：(m+1)ϕ(n)≡1(m+1)^{\phi(n)} \equiv {1}(m+1)ϕ(n)≡1 (mod(mod(mod n)n)n)。
当然这可能不是最小的，我们预处理出n−1n-1n−1的质因数，从大到小试除即可，这样写最简单。
时间复杂度O(Tlog2n)O(T \log^2 n)O(Tlog2n)，最大只跑了800多ms。
代码：
SUGAR SWEET II
树上BFS期望题：
考虑期望递推式子：E(i)=ai+wi∗P(i)E(i) = a_i + w_i * P(i)E(i)=ai +wi ∗P(i)，从中我们可以将每个 iii 分成三种人：
* 类型0：永远都提升不了的人，即满足 ai≥abi+wbia_i \ge ab_i + wb_iai ≥abi +wbi 的人，所以 P(i)=0P(i) = 0P(i)=0。
* 类型1：一定能提升的人，即满足 ai<abia_i < ab_iai <abi ，此时 P(i)=1P(i) = 1P(i)=1。
* 类型2：可能能提升的人，即满足 ai∈[abi,abi+wi]a_i \in [ab_i, ab_i + w_i]ai ∈[abi ,abi +wi ]，这种需要进一步考虑。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如何处理类型2情况？
考虑到如果类型2想要提升，必须满足 posbi<posipos_{b_i} < pos_iposbi <posi 且 bib_ibi 一定提升，又因为每个人只有一个 bib_ibi ，约束关系可以形成多条相交但互不影响的链，约束的对象不是类型2的人结束。
即：
i→x1→x2⋯→X,X∉类型2i \rightarrow x_1 \rightarrow x_2 \dots \rightarrow X, \quad X \notin \text{类型2} i→x1 →x2 ⋯→X,X∈/类型2
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
分讨一下 XXX 的情况
* XXX 是类型0：全链 P=0P = 0P=0。
* X=iX = iX=i：导致全链关系矛盾，P=0P = 0P=0。
* XXX 为类型1：若 iii 想提升，则一定全链是发生由后到前，呈唯一排列顺序，此时的 P(i)=1m!P(i) = \frac{1}{m!}P(i)=m!1 ，mmm 为全链元素个数。
所以我们就可以知道，如果一个类型2点经过 ddd 条边到一个类型0点，则 P(i)=1(d+1)!P(i) = \frac{1}{(d+1)!}P(i)=(d+1)!1 。
这样我们就做完了。
CF2205E
首先我们得转化一下思路，题目中问有多少不同SSS可以变为TTT，按照翻转的性质，我们可以转化为TTT可以转化为多少不同的S′S'S′，这样就变成了一个正向计数题。
考虑一个Str=M+B+MStr=M+B+MStr=M+B+M的问题，分两种情况：
1.rev(Str)=[M+B+M]R=rev(M)+rev(B)+rev(M)rev(Str)=[M+B+M]^R=rev(M)+rev(B)+rev(M)rev(Str)=[M+B+M]R=rev(M)+rev(B)+rev(M)
2.rev(Str)=[M]R+[B]R+[M]R=rev(M)+rev(B)+rev(M)rev(Str)=[M]^R+[B]^R+[M]^R=rev(M)+rev(B)+rev(M)rev(Str)=[M]R+[B]R+[M]R=rev(M)+rev(B)+rev(M)
所以这两种所产生的贡献是一样的，所以只有BorderlessBorderlessBorderless的串才能产生贡献。
既然这样，再回看题目，长序列计数问题，最常用dpdpdp或者组合计数，观察数据范围，我们可以大胆猜一下用一个O(n2)O(n^2)O(n2)的dpdpdp去解决。
dpjdp_jdpj 表示S[1...j]S[1...j]S[1...j]的方案数，我们可以采用推表的方法，枚举i=j+1...ni=j+1...ni=j+1...n，用KMPKMPKMP判断S[j....i]S[j....i]S[j....i]是否为BorderlessBorderlessBorderless，即nxti=0nxt_i=0nxti =0。再加上本身的方案数即可。
ARC191C
神秘数论脑电波题目。。。。
结论是(A,M)=(N+1,N2)(A,M)=(N+1,N^2)(A,M)=(N+1,N2)
浅浅证明一下吧：
1.为什么可行？
(N+1)N−1=∑k=1NCNk×Nk(mod(N+1)^N-1=\sum_{k=1}^{N}{C_{N}^{k}\times N^k} (mod(N+1)N−1=∑k=1N CNk ×Nk(mod N2)N^2)N2)
当k≥2k\ge 2k≥2时，NkN^kNk一定包含N2N^2N2因子，所以取模为000。
所以可以转化为(N+1)N−1=N2≡0(mod(N+1)^N-1=N^2 \equiv 0(mod(N+1)N−1=N2≡0(mod N2)N^2)N2)。
2.为什么是最小？
令1≤n<N1\le n < N1≤n<N，(N+1)n−1=∑k=1nCnk×Nk(mod(N+1)^n-1=\sum_{k=1}^{n}{C_{n}^{k}\times N^k}(mod(N+1)n−1=∑k=1n Cnk ×Nk(mod N2)N^2)N2)
根据上面结论，显然答案在模N2N^2N2意义下为nNnNnN，再看nnn的范围，显然不是倍数，得证。
模拟赛的一道题
观察1h后，发现vvv的值比较小，说明每个数最大贡献为100010001000，当区间长度为kkk的情况下，整个区间最大贡献为1000×k1000\times k1000×k
，而整个区间的子集个数为2k−12^k-12k−1，根据鸽巢定理，如果2k−1>1000×k2^k-1>1000 \times k2k−1>1000×k，所以当k≥14k\ge14k≥14，一定找出满足题意的XXX和YYY。
如果<14<14<14，用一个bitset判一下即可，位运算非常的快。
那待修也比较好想，因为有一个取模，不好直接做。用差分树状数组维护某个数立方次数，再预处理出某个数立方次数为kkk对vvv取模的值，这样就做完了。
持续更新中........
