11.29
在机房训练的最后一天
做了点儿彩色绿题，学了下 2-sat，打了会儿板子，把 D 盘收拾了一下，带走了所有东西。
默念：不考高精，不考大模拟……不考拉插……
11.30
高二了，退无可退
6.30 起床，吃的饺子。
8:00 赶到考场。同学已经在了，西工大附中还是很有牌面的，拉了个大横幅 ccf noip2024 考点。
8.25 左右进的考场，机况很好，键盘很屎，比 csp 好在左右有个挡板，不过地方贼小，胳膊都伸不开，演草纸没地方放，难受。
8.30 开题，浏览一遍，发现没有天天。
看 T1， WC 有点吓人。瞪了 10min 没思路。然后陆陆续续听见贼多敲键盘的声音，你们是不是都会了啊？！直接慌掉了。然后思路就有了。维护出来所有连续的 1 的段，然后对每个 1 段开桶，统计在这个段里对应的有多少 0,1。然后对每个点打上标记，看这个点属于哪一个段。然后一位一位遍历匹配，如果两个字符串的这个位置的所属段都有标记，并且对应桶里都有 1 或者都有 0，那就把 1 或 0 分别减掉 1，如果一个在段里一个不在，那就对标不在段里的那个字符。大样例直接放过去了。40min搞定。
我左边的那个哥们在吃手。
看 T2，发现没读懂题。然后翻了翻 T3T4，还是滚回来做T2吧。艰难的理解完题意之后，初步推断每一位上是不受任何影响的，我们称有一元关系的位置为关键位置，然后如果有两个相邻的关键位置那就 \(\times [v(v-1)+1 ]\)，没有的话就 \(\times v^2\)，测个大样例，被 \(129600\) 卡了。我们称两个最近关键位置之间形成的段为一段，那么这一段里的贡献并不是上述那样。尝试分解了一下 \(129600\) 的质因数，发现有一个 \(5\) 在里面，这个 \(5\) 肯定是加出来的，那么尝试使用 dp。考虑在这么一段里 dp，令 \(f_{i,1}\) 表示如果这个位置是关键点并且形成的段长为 \(i-1\) 的方案数，\(f_{0,i}\) 表示这个位置不是关键点并且段长为 \(i-1\) 并且段末端是关键位置的方案数，那么有：
\[\begin{split} f_{i,0}=&v^2\times f_{i-1,0}\\ f_{i,1}=&v\times f_{i-1,1}+v(v-1)\times f_{i-1,0} \end{split} \]矩阵快速幂优化即可。也是出了 \(129600\)。
我左边的那个哥们在吃手。
还有 1h，打了T4暴力，唐氏没想到预处理，然后 \(<=5000\) 的点没吃上。打了个 T3 骗分，似乎挂掉了。
不知为甚我的 dev 会在编译之后未响应一段时间，仅限暴力代码会这样。
然后再 “乌邦图” 里跑了，没问题，就填表打包了。
\(100+100+0+10=210\)，别挂求求啦
结束后听说 t1 很多人没出来，不知道在敲啥键盘
标签：noip,位置,T2,然后,times,2024,游记,100,129600 From： https://www.cnblogs.com/xiaolemc/p/18579120