1010
ZRC签到 想到了等于是一种特殊情况然而判反了wa了一发…
1012
题意：
给一个1e5的小写字符串(多组，总长5e6)，问字符串所有区间的权值和。权值为每个不同字符的个数的平方。
ZRC卡常解：
不管怎么看这题都是一个签到题的样子。考虑5e6允许我们带一个常数或者极小的log。对于26个字母分别求解，将原数组化为01数组，把式子列出来，把值用前缀和表示，就可以得到一个O(n)的处理前缀和以及前缀前缀和的做法。方法比较无脑，然而被卡常了。好像常数优秀的话能过。
WD正解：
设字符串第i位的字符为c，最终答案为sans(sum of ans)，在i处结尾的区间的总答案为$ans_i$，在当前位置结束的区间的答案当中字母$c$的贡献为$a[c]$，第$j$个字符$c$的位置为$pos[j]$。
那么，显然$ans_i=ans_{i-1}-a[old\ c]+a[new\ c]$
如何维护$a$数组呢
$$
a[old\ c]=\sum ^ { j-1 } _ { k=1 } (pos[k]-pos[k-1])\cdot(j-k)^2\\
a[new\ c]=\sum ^ { j } _ { k=1 } (pos[k]-pos[k-1])\cdot (j+1-k)^2\\
$$
可以发现，这两个式子有很大的相似性，考虑差分
$$
a[new\ c]-a[old\ c]=(pos[j]-pos[j-1])+\sum _ { k=1 } ^ { j-1 } (pos[k]-pos[k-1])\cdot(1+2j-2k)\\
=pos[j]-pos[j-1]+\sum _ { k=1 } ^ { j-2 } pos[k]\cdot((1+2j-2k)-(1+2j-2(k+1)))+pos[j-1]\cdot 3\\
=pos[j]+\sum _ { k=1 } ^ {j-1} pos[k]\cdot2\\
$$
即可方便维护
题解：
与上面方法相似，但$pos[k]-pos[k-1]$用$len[k]$来表示，因此最终式子推起来复杂一些
1007
LYF 签到
题意就是找数列中环的平均值。但有些点可能会指向环而自身不属于环
1003
LYF 根据题目性质简单推式子即可，运算过程中似乎需要注意一下精度
1008
ZRC大模拟 没啥好说的
1005
题意：
1e5个询问，每个询问包含一个n(1e6)。询问表示有n个座位。不断会有人来，等概率随机挑一个相邻位置无人的、与最近的人最远的位置坐下。问期望能坐几个人。
LYF&WD解：
首先根据数据范围可以想到，大致应该做到预处理+O(1)询问。考虑将区间分为三类，分别为两端受限制、一端受限制、两端不受限制。只有初始没坐人的区间才属于第三类。定义完后推式子就很简单：
$$
f[i][0]=f[i/2][0]+f[i-i/2][0]+1\\
f[i][1]=f[i-1][0]+1\\
ans[x]=\sum _ { i=1 } ^ { n } \frac{1}{n}\cdot(f[i-1][1]+f[x-i][1]+1)\\
=1+\frac{2}{n}\cdot\sum _ {i=1} ^ { n-1 } f[i][1]
$$
前缀和即可
1004
题意：
n1e6，有2n个桶，可以从第2x个桶里面拿到0~x个球，从2x+1个桶里拿到kx个球。问拿m1e6个球有多少种取法。
LYF解：
为什么题目要将桶的数量设置成必定是偶数？考虑配对。对相邻两个桶一起看成一个大桶，则这个大桶可以取任意个球，且均只有一种取法。因此问题就变成了一个简单的组合数学问题。
1006补
题意：
有个人丢手雷，三维随机方向等概率丢出，丢出的速度为v0，重力加速度10，手雷伤害半径为r。丢出手雷后人不动，问手雷是否会伤人。
解：
首先将情况建模成两个球的交，然后余弦定理+积分。
赛场上的思路非常弯折。首先我想到可以搞成两个球的交的问题，但是没往求角度的方向想，由于上次计算几何题目球冠公式中有个球冠高度，因此我也只想着先得到球冠高度。没有标清楚已知量导致我没看出来能用余弦定理，只是不停地用勾股定理算。算到一半还没算出来就被WD否了方法，转而用王鼎的推公式法。用推公式法原本是很顺利的，结果又进了个误区：三维任意角度抛出的话，球当中截一个圆，角度并非均匀分布。WD说的“概率密度函数”之类的概念我没听说过，但是其实这并不会妨碍我正常推式子（别的概率题我也是有能力直接推的，只是不知道这个概念，但用的都是这一套操作），但是让我更怀疑自己是否能成功推式子的能力。（但是对于有些情况确实不知道知识点就没法搞，看起来像搞出来了，结果也是错的）在角度均匀分布的错误假设下，我只能得到答案包含三角函数/反三角函数的结论，与题意显然不符。事实上在这里正确的概率就是应该算表面积。对着一个sin猜了个公式，结果WA；WD重新推了个式子，仍然是WA。但是谁能想到问题在我的特判上，两个球相离，答案是0；两个球相交，答案正常计算；两个球相包含，要分两种情况，而我只分了一种，爆炸。最后就没过。
吃一堑长一智吧
还有一个问题就是 在模意义下计算时不需要像某些物理或者数学题一样尽量把分子分母拆掉，只需要把真正公有的因式除掉就好了。这样可以少求几次逆元，且写代码也更方便。