【PHT】2022-10-21
传送门
T1 算贡献
T2 算贡献+矩乘维护动态dp
T3 类似于 CCPC2021 K ，用矩乘维护斐波那契和
T4 妙题，就是先让
x[i]=A[i]-B[i]，然后显然就是要判断何时 \(\forall\)x[i]=0，然后就是感性理解一下就是判断的条件是很紧的，非常唯一，然后你每次直接操作都非常的繁琐，考虑变换一下使得我的操作不要那么繁琐，就是y[i]=x[i]-x[i-1]-x[i-2]然后发现这样每次操作就只要弄l,r即可，这类题好像xtq讲过 ??
T5 随机化
T6 拓展欧拉定理，类似于 【
P4139 上帝与集合的正确用法】
T7 简单退一下式子发现是等比数列求和然后就是模意义下求对数，
bsgs
T8 不难但是挺难的题，就是两个方向，要么优化贪心，要么大力多项式，至于贪心的证明就是非常典的染色游戏什么的。
多项式做法，就是每个位置要么操作要么不操作，就是一个无穷长的
0/1串，设为 \(F(x)\) 然后你的结果就是 \(F(x)*S(x)\) 其中加号是异或，乘号是与，然后就是列出形如 \(F(x)*S(x)=1+x^k\) ，然后就是bsgs。
优化贪心，就考虑整个过程虽然是在动态调整的，但是结果都是确定的，然后就以动态调整作为阶段来dp，设 \(f[i][j]\) 表示窗口滑到 \(i\) 且 进行操作完毕后 窗口内第 \(i\) 个数的值，然后又递推式：
\[\begin{aligned}
f[i][j]=
\left \{
\begin{aligned}
f[i-1][j+1] ,f[i-1][2]=0\\
f[i-1][j+1] \operatorname{xor}s_j,f[i-1][2]=1
\end{aligned}
\right .
\\
\rightarrow f[i][j]=f[i-1][j+1]\operatorname{xor} (s_j\&f[i-1][2])
\end{aligned}
\]
是一个矩乘状物，然后就是形如等式 \(A[] * Tr[]^k=D\) ，
bsgs again