[总结]2023-1-7B组模拟赛
P0 前言
感觉比赛状态回来了，但是思维还没上来。
P1 心路历程
又是先全部看题。T1有点奇怪，没有多想。T2看到数据感觉有70pts的 \(n^2\) dp。T3准备好50pts最短路乱搞。T4明显有暴力35pts+循环节35pts，最后30pts没看出来。
先打T2。设状态 \(f(i,j)\) 为第i天能量为j的最大价值，转移显然 \(f(i,j)=\max(f(i-1,j)+j,f(i-1,j-1))-a[i]\)。就是昨天是否能量到达了j。注意一下如果\(f(i-1,j)\)或者\(f(i-1,j-1)\) 为负数则不能取负数那一个。初始化注意一开始的能量只能是L，大于L的不行。即\(f(0,L)=0,f(0,L+1\to L+n)=-\text{INF}\)。并且第二维显然是\(L\to L+n\)，可以拿数组存实际数值，第二维存这个数值在这个数组的下标。
接着T1。看完样例显然当n=2时有解，又根据题目当\(a[i]=a[j]\) 时可以减少一个堆，就有两种方式进行操作。第一种，如果\(a[i]+[j]=2^x\)，就while搞；第二种，如果有$a[i]=3 \cdot a[j] $ 或者 \(a[j]=3 \cdot a[i]\)，搞i,j。当然，数据还可能没有这两种。那么就随机数乱搞。这些操作都要无限循环直到满足只剩一堆。
然后T3。太久没打priority_queue+Dij，有点慌。不过最后默写完了。还补了一个没有用dfs。
最后T4。我当然知道他有循环节，但是我居然不太会。（？）就是担心那种前面几个不是循环节的那种数列。打了个35pts的暴力，最后在那算，搞半天数学无果。
P2 赛后情况
T1、T2没问题，T3、T4爆0！
T4的模数没有模完整，T3输入问题！
我是个**，\(185 \to 100,\text{rank 8}\to\text{rank31}\)。
P3题目分析
T1
网上正解太骚，同学讲的还行。
考虑奇偶性。显然有偶数个石子数为奇数的堆。那么，不妨让每两个奇数堆进行操作，偶数堆不理。操作完后全体堆的石子数除以2。因为它们本质上是一样的。除完后显然还有奇数，继续这样做，直到只剩一堆或者说是只剩一个石子。
T2
贪心。考虑两种情况。一种是不够吃，一种是够吃。
先考虑后者。那么够吃有两种选择。第一种：升级。第二种：制造食物。所以什么时候升级、什么时候制造食物是一个需要考虑的问题。设当前是第x天，前x天都升级，后n-x都制造食物。显然这样做的答案为 \((L+x)(n-x)\)。其他题解说当\(L+x<n-x\)时就升级，否则就制造食物，我也不知道为啥。
再考虑前者。不够吃只能被迫制造食物。如果这一天制造完了后还不够，那么就需要前面升级的天制造食物。-1情况显然。
所以设add为当目前为止升级的天数，x为现在是第几天。那么第一种情况很简单，第二种情况就变成了\(L+add<n-x\)时升级。
T3
正解斜率优化dp。状态还算简单，设\(f(i)\)为到i城市的最小代价，则有 \(f(i)=\min_{j>i}\{f(j)+(j-i)\cdot a[i]+b[j]\}\)。这是倒推的做法，可以理解为所有的边反着建，从n城市推到1城市。
考虑j<k且选j点比选k点优。则有\(f(j)+(j-i)\cdot a[i]+b[j]<f(k)+(k-i)\cdot a[i]+b[k]\)，化简，得\(f(j)+a[i]\cdot j+b[j]<f[k]+a[i]\cdot k+b[k]\)。再设\(g(i)=f(i)+b[i]\)，带入得\(g(j)+a[i]\cdot j<g(k)+a[i]\cdot k\)。
\[g(j)+a[i]\cdot j<g(k)+a[i]\cdot k \\ -a[i]\cdot (k-j)<g[k]-g[j] \\ -a[i]<\dfrac{g[k]-g[j]}{k-j} \\ \dfrac{g[k]-g[j]}{k-j}>-a[i] \]那么，左边就是过点\((k,g[k]),(j,g[j])\) 的斜率。斜率大于\(-a[i]\)说明j比k优。此时就可用单调队列来维护点集，需要一个最优点时二分即可。但我不知道为什么要用单调递减的队列。
T4
分为3个档，第一个暴力，第二个找循环节，第三个数学。
来说一下第三个。就是一个配方思想加上题目给的条件。
设 \(x=x_i,y=x_{i-1}\)，则
\[\begin{align} x&=ay^2+by+c\\ x&=(ay^2+by+\dfrac{b^2}{4a})-\dfrac{b^2}{4a}+c\\ x&=a(y^2+\dfrac{b}{a}y+\dfrac{b^2}{4a^2})-\dfrac{b^2}{4a}+c\\ x&=a(y+\dfrac{b}{2a})^2-\dfrac{b^2}{4a}+c\\ x+\dfrac{b}{2a}&=a(y+\dfrac{b}{2a})^2+\dfrac{2b-b^2}{4a}+c\\ x+\dfrac{b}{2a}&=a(y+\dfrac{b}{2a})^2\\ a(x+\dfrac{b}{2a})&=[a(y+\dfrac{b}{2a})]^2 \end{align} \]我们现在来仔细看一下这个式子\(a(x+\dfrac{b}{2a})=[a(y+\dfrac{b}{2a})]^2\)，不放把 \(x=x_i,y=x_{i-1}\)带进去，得\(a(x_i+\dfrac{b}{2a})=[a(x_{i-1}+\dfrac{b}{2a})]^2\)。我们知道\(4ac=b^2-2b\)，所以\(c=\dfrac{b^2-2b}{4a}\)，而且\(x_{i-1}=ax_{i-2}^2+bx_{i-2}+c\)，再带进去，得
\[\begin{align} a(x_i+\dfrac{b}{2a})&=[a(ax_{i-2}^2+bx_{i-2}+\dfrac{b^2-2b}{4a}+\dfrac{b}{2a})]^2\\ a(x_i+\dfrac{b}{2a})&=[a(ax_{i-2}^2+bx_{i-2}+\dfrac{b^2}{4a}]^2\\ a(x_i+\dfrac{b}{2a})&=[a^2(x_{i-2}+\dfrac{b}{2a})^2]^2\\ a(x_i+\dfrac{b}{2a})&=[a(x_{i-2}+\dfrac{b}{2a})]^{2\times2}\\ a(x_i+\dfrac{b}{2a})&=[a(x_{i-2}+\dfrac{b}{2a})]^4 \end{align} \]我们仔细观察一下这两个东西：
\[a(x_i+\dfrac{b}{2a})=[a(x_{i-1}+\dfrac{b}{2a})]^2\\ a(x_i+\dfrac{b}{2a})=[a(x_{i-2}+\dfrac{b}{2a})]^4 \]注意到右边的指数和下标有一种关系，具体来说，就是：
\[a(x_i+\dfrac{b}{2a})=[a(x_{i-p}+\dfrac{b}{2a})]^{2^p} \]这个也可用归纳法证明。所以，可以得到
\[\begin{align} a(x_n+\dfrac{b}{2a})&=[a(x_0+\dfrac{b}{2a})]^{2^n}\\ x_n&=\dfrac{[a(x_0+\dfrac{b}{2a})]^{2^n}}{a}-\dfrac{b}{2a}\\ x_n&=a^{2^n-1}\cdot (x0+\dfrac{b}{2a})^{2^n}-\dfrac{b}{2a} \end{align} \]但是指数太大会爆掉怎么办？题目给定m为质数，而又让你去模m，于是我们想到费马小定理：当\(m\)是质数时，并且\(m\nmid a\)时，则有\(a^{m-1}\equiv 1(\bmod m)\)。于是我们可得 \(a^{2^n-1}\equiv a^{(2^n-1) \bmod (m-1)} (\bmod m)\)。
可以假设\(a^{k(m-1)}\cdot a^{2^n-1-k(m-1)}=a^{2^n-1}\)，其中\(k=\lfloor \dfrac{2^n-1}{m-1}\rfloor\)。我们知道\((p_1\cdot p_2)\bmod q=p1\bmod q\cdot p_2\bmod q\)，于是\(a^{2^n-1}\bmod m=a^{k(m-1)}\bmod m\cdot a^{2^n-1-k(m-1)}\bmod m\)，然后\(a^{k(m-1)}=[a^{(m-1)}]^k\)。根据同余定理：如果\(a\equiv b(\bmod q)\)，那么\(a^k\equiv b^k(\bmod q)\)；并且\(a^{m-1}\equiv 1(\bmod m)\)，所以\([a^{m-1}]^k\equiv 1^k\equiv 1(\bmod m)\)。
所以\(a^{2^n-1}\bmod m=a^{2^n-1-k(m-1)}\bmod m\to a^{2^n-1}\equiv a^{2^n-1-k(m-1)}(\bmod m)\)，根据余数的定义，\(2^n-1-k(m-1)\)就是\(2^n-1\bmod(m-1)\)。所以得到了\(a^{2^n-1}\equiv a^{(2^n-1) \bmod (m-1)} (\bmod m)\)。
P4 总结
题目都是打起来不难，想起来比较难。尤其是T4，推导和证明真的很难。下次要检查检查程序，不要再丢分了。并且要加强联系斜率优化的题目。
标签：7B,cdot,dfrac,bmod,2a,2023,4a,模拟,equiv From： https://www.cnblogs.com/xmtxlym/p/17036326.html