https://codeforces.com/contest/1951

G Clacking Balls(2s,256mb)

1~m篮子 顺时针 环

n个球，第i个在 篮子ai中，每个篮子至多1个球

alice 可以进行1s操作

• [1,n]等概率 选i
• 如果 球已经不存在，则跳过（依然耗时）
• 如果 球存在，则沿着把球顺时针移动一个篮子，（如果目标篮子有球，把目标篮子中原来的球抛弃）

直到只剩下一个球停止，求操作时间的期望值 mod 1e9+7

n 3e5

n,m 1e9

我的思路

不能说没有想法，只能说一点想法也没有

如果一个球消失，那么说明有前面的球超过了它，换个角度 如果 球i移动 导致球j消失，也就是i走到j的位置，那么换成i消失是等价的后续，不影响概率

所以转换了题意的第三条（谁移动谁消失）以后

如果说 最后剩下的是 第i个球，那么这个球没有触碰下一个球，而前面的所有球触碰了后一个球

所以是个min/max 容斥+期望 吗？

计算每个球的 消失(触碰后面球)的期望次数，再min-max 容斥掉?

感觉也不对

再换个角度， 如果i留下

1

[i-1 ................i] .....

没啥想法，总的来说，显然直接状态描述肯定不行的，不论是点坐标还是距离

那么要么就是孤立每个 间隔的期望什么的，要么就是孤立的什么点期望，总之需要一个办法把其中 关联的东西拆掉，

而且不只如此，还有环

然后就是考虑简化的问题， 同样是环，但是只有两个点

那么 Exp(state) = Exp(点的距离)

然而转化构成了 一个转化矩阵

$A\lambda=\lambda$的形式，已知$A$要求$\lambda$

另一个是展开环到无限的数轴，指定目标点，那么得到每个点的移动方案数？

https://codeforces.com/contest/1943

D1,D2 Counting Is Fun

如果数组 每次可以 选择连续长度大于1的区间 同时减去1,操作多次以后 所有值变为0,则该数组是好（good）数组

对于 长度n,值范围[0,k]的 $(1+k)^n$个数组有多少个是好数组 $\mod p$

n D1(400),D2(3000)

$\sum n^2$, D1(2e5),D2(1e7)

$k \le n$

$p\in[10^8,10^9]$ 是质数

3s

1024mb

我的思路

good的充要条件？

首先 两端 不大于a1

如果出现连续3个$a < b > c$

要$b-a\le c$ (b,c同时下降 直到b变为a)或$b-c\le a$ (a,b同时下降 直到b变为c)

都是$b\le a+c$

所以 如果good 一定满足 上面的 两端 和 单峰的条件

那么如果满足 两端 和 单峰条件

对于单峰从左到右, 下降，每个前面的不影响后面的，

因此 这个条件是充要

就dp吧

dp[i][x][y]= 前i-1个位置合法，第i-1个位置是x,后一个是y的方案数

从第二项开始

然后 ans = sum dp[n][>=x][x]

对于$x\le y$

dp[i+1][x][y] = sum dp[i][...][x]

对于$x > y$

dp[i+1][x][y] = (sum dp[i][t][x], x <= t+y )=sum dp[i][>=x-y][x]

所以

dp[i+1][x][y] = sum dp[i][>=x-y][x], 其中 dp[i][<0][x]=0

用 后缀和可以 均摊 O(1) 计算每个x,y

所以有一个 $n n^2$的方法，感觉能过D1, 然后D2 明显TLE

感觉就是需要再次优化效率，然而上面的似乎并不能nxn的矩阵的矩阵乘法

然而 并没有成功优化

https://ac.nowcoder.com/acm/contest/76652

D S 老师的虚树

给n点定树T，边有颜色

对于 点集S,包含点集S的最小连通点集V’对应的树为生成树T’

w(S)=T’中不同颜色边个数

对于 i=1..n

计算 |S|=i的w的期望Exp(w(S)),结果mod 998244353

n 2e5

2s

512mb

我的思路

感觉就是算贡献，对于点为i的 点集合，对于颜色c的所有边来说，如果有横跨 边的两个点，那么贡献1,否则贡献0

那么考虑不跨边更简单，也就是 贡献i,c=所有情况 - 不跨边

$= \binom{n}{i}-\sum_{blk_j} \binom{blk_j}{i}$ 其中 blk是按照指定颜色切割的块

那么 $ans_i= C\binom{n}{i}-\sum_{blk_j} \binom{blk_j}{i}$,其中C是颜色总个数,blk是所有颜色独立的切割

那么问题来了，每个颜色切割的块数 = 当前颜色边数+1,

所以右侧有 n+C个 <=2n, 但是直接计算，对于每个i来说复杂度也是 $O(n)$的,总的复杂度会tle

生成函数我也想过没想过怎么简化

https://codeforces.com/contest/1936

D. Bitwise Paradox

对于给定$v$

长度$n$,正整数数组$a,b$

对于$[l,r]$若 $b_l | b_{l+1} | \cdots | b_r \ge v$, 则称区间$[l,r]$是好的，其中运算符是 bitwise or运算

区间美丽值$beauty([l,r])=\max(a_l,a_{l+1},\cdots,a_r)$ 且区间是 好的，否则为$\infty$

q个询问,两种操作

• 单点修改b, $b_i=x$
• 询问$[l,r]$的所有子区间中 最小的美丽值（好的子区间中最小的美丽值）

n,q 2e5

$a_i,b_i,v \in [1,10^9]$

5s

1024mb

我的思路

首先b是控制是否good, 而a是控制beauty的最大值的

先是想如果没有操作就是询问

那么注意到 最这[l,r] 增大 bitwise or 非严格单调递增，同时beauty也非严格单调递增

所以想for l=1..n, 对于每个 l 找最小的r使得它是good 的，

那么 对于[ql,qr],如果ql <= l, 那么以l为子区间左端点的贡献就是 最小的r，包裹起来的 a的max

因为 如果 qr < r，说明以$l$为起点的 任何区间都非good,无贡献，

如果qr>=r,说明l作为子区间左端点时，有且只有r..qr作为子区间右端点的贡献，而r是一定非严格最小的，所以r+1..qr不会有额外贡献

所以 可以预先处理成 [i]=>[r,max]

计算r就是 直接 做bit拆分的 每个bit求和 做比较， n logV复杂度，r随着i增加非严格单调递增，max是丢个优先队列，能同步完成的

那么查询就是 [ql,qr] 中 所有 min(max) |{r <= qr,max}

这可能要离线莫队

然后如果把上面n个 [l,r,max] 看成n次操作的话

那么实际上是二维平面里 [<=l, >=r]的地方 做了val=min(val,max)的运算

也可以 2d seg tree

然后问题来了，现在虽然不改动a,但是要改动$b_i=x$

而一个bi 将 影响那些 l <= i <=r的

这样 修改的 [l,r,max] 就是多个了

没想到怎么维护

二次剩余

定义

$x^2\equiv a\pmod{p}$

若有解$a$为二次剩余，否则为二次非剩余

性质

二次剩余 乘 二次剩余 = 二次剩余， 显然

二次剩余 乘 二次非剩余 = 二次非剩余， 显然

二次非剩余 乘 二次非剩余 = 二次剩余, 暂时无法证明，后续证明

$1\cdots p-1$中有$\frac{p-1}{2}$个二次剩余 和 $\frac{p-1}{2}$个二次非剩余

二次剩余 $1^2,2^2,\cdots,(\frac{p-1}{2})^2$， 显然包含所有，且都是二次剩余，且两两不等

延伸

勒让德符号(legendre symbol)

$xy\equiv a\pmod p$

显然 对于 给定x,只有唯一$y\equiv ax^{-1}\pmod{p}$

如果a二次非剩余，所以每个x配对的都不是x自己，所以是p-1个有序的不等的配对$(i,ai^{-1})$,

而 每个(x,y)对应也有一个(y,x), 所以是$\frac{p-1}{2}$对 前后可以颠倒的

把所有(x<y)的xy全部乘起来 $(p-1)!\equiv a^{\frac{p-1}{2}}\pmod{p}$

a是二次剩余, x是解,p-x也是解，显然只有这两个是解

所以$\frac{p-1}{2}-1$对 前后不等可交换的，和$(x,x),(p-x,p-x)$

同样 成对的只选(x<y)的全部乘起来，$(p-1)!\equiv a^{\frac{p-1}{2}-1}x(p-x)\equiv -a^{\frac{p-1}{2}-1}x^2\equiv-a^{\frac{p-1}{2}}\pmod{p}$

由上面的性质 引入 勒让德符号(legendre symbol): $\left(\frac{a}{p}\right)$

$=1$则$a$是$\pmod{p}$二次剩余

$=-1$则$a$是$\pmod{p}$二次非剩余

所以$(p-1)!\equiv -\left(\frac{a}{p}\right)a^{\frac{p-1}{2}}\pmod{p}$，即

推论

威尔逊定理$(p-1)!\equiv -1\pmod{p}$

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}$, 因此可以快速知道一个数是否是$\pmod{p}$的二次剩余，本章节核心

由此 我们知道

$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\equiv a^{\frac{p-1}{2}}b^{\frac{p-1}{2}} \equiv (ab)^{\frac{p-1}{2}}\equiv \left(\frac{ab}{p}\right) \pmod{p}$, 也就是勒让德符号的乘法分配率，也证明了上面的 两个二次非剩余的乘积是二次剩余

$\left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}\pmod{p} = (-1)^{\frac{p-1}{2}}$

所以$p=4n+3$则$-1$不是二次剩余,如果$p=4n+1$则$-1$是二次剩余

$\gcd(a,b)=1$则$a^2+b^2$的素因子都是$4n+1$型

反证: $p=4n+3,p|a^2+b^2$,

$a^2\not\equiv 0\pmod{p}$

$b^2\not\equiv 0\pmod{p}$

$a^2+b^2\equiv 0\pmod{p}$

$-a^2\equiv b^2 \pmod{p}$

$-1 \equiv b^2(a^{-1})^2 \pmod{p}$

$-1 \equiv (ba^{-1})^2 \pmod{p}$, 这说明 -1是二次剩余

$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = (-1)^{2n+1} = -1$， 这说明-1是二次非剩余，矛盾

高斯引理

例子: $\left(\frac{2}{p}\right)=2^{\frac{p-1}{2}}\mod p$

$a=1,2,\cdots,\frac{p-1}{2}$

$b=2a=2,4,\cdots,p-1$

$2^{\frac{p-1}{2}}(\frac{p-1}{2})!=\prod b=(\frac{p-1}{2})!(-1)^{\mathrm{count}(\mathrm{even} > \frac{p-1}{2})}$, 对于 $> \frac{p-1}{2}$的用$p-(p-v)$替换

$2^{\frac{p-1}{2}}=(-1)^{\mathrm{count}(\mathrm{even} > \frac{p-1}{2})}$

$p=4n+3$是$\left(\frac{2}{p}\right)=(-1)^{n+1}$

$p=4n+1$是$\left(\frac{2}{p}\right)=(-1)^n$

再细分

$p=8n+1,\left(\frac{2}{p}\right)=1$

$p=8n+3,\left(\frac{2}{p}\right)=-1$

$p=8n+5,\left(\frac{2}{p}\right)=-1$

$p=8n+7,\left(\frac{2}{p}\right)=1$

所以$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$

一般化:

$\left(\frac{m}{p}\right)$

$a=1,2,\cdots,\frac{p-1}{2}$

$b=ma=1m,2m,\cdots,\frac{p-1}{2}m$, 两两不同余

$\mu_{m,p}=$ 数列$b$中$\mod p$后$> \frac{p-1}{2}$的个数

$\left(\frac{m}{p}\right)=(-1)^{\mu_{m,p}}$

二次互反律

二次也就是上面二次剩余的二次，也就是legendre符号要判定的内容

$p,q$是两个不同奇素数则$\displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

好处，计算时,可以辗转 反复颠倒 从而快速算出p,q都很大时的 结果

埃森斯坦的证明法

$\displaystyle \frac{p^2-1}{8}q = \sum_{i=1}^{\frac{p-1}{2}} iq$

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}}([\frac{iq}{p}]p+r_i)$, 写成余数和商

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+\sum_{i=1,r_i\le \frac{p-1}{2}}^{\frac{p-1}{2}} r_i+\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} r_i$, 根据$r_i$大小拆分

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+\sum_{i=1,r_i\le \frac{p-1}{2}}^{\frac{p-1}{2}} r_i+\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-(p-r_i))$, 把$r_i$转化成为$[1,\frac{p-1}{2}]$

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+\sum_{i=1,r_i\le \frac{p-1}{2}}^{\frac{p-1}{2}} r_i+\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} p-\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-r_i)$, 把$r_i$转化成为$[1,\frac{p-1}{2}]$

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+\sum_{i=1,r_i\le \frac{p-1}{2}}^{\frac{p-1}{2}} r_i+\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-r_i)+\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} p-2\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-r_i)$, 拆出2倍

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+\sum_{i=1}^{\frac{p-1}{2}} i+p\mu_{q,p}-2\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-r_i)$, 处理(2+3),4项

$\displaystyle =\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+\frac{p^2-1}{8}+p\mu_{q,p}-2\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-r_i)$, 处理第2项

$\displaystyle \sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]p+p\mu_{q,p}\equiv \frac{p^2-1}{8}(q-1) +2\sum_{i=1,r_i > \frac{p-1}{2}}^{\frac{p-1}{2}} (p-r_i) \equiv 0\pmod{2}$, 奇偶性

$\displaystyle \sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]+\mu_{q,p}\equiv 0\pmod{2}$, 奇偶性

$\displaystyle \left(\frac{q}{p}\right)=(-1)^{\mu_{q,p}}=(-1)^{\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]}$ 利用高斯引理

$\displaystyle \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]+\sum_{i=1}^{\frac{q-1}{2}} [\frac{ip}{q}]}$ 对称带入

$\displaystyle \sum_{i=1}^{\frac{p-1}{2}} [\frac{iq}{p}]+\sum_{i=1}^{\frac{q-1}{2}} [\frac{ip}{q}]$ 在二维平面中表示的是 $y=\frac{q}{p}x$ 这条线下方和上方，与$x=1,y=1,x=\frac{p-1}{2},y=\frac{q-1}{2}$ 围成三角形边界和内部的格点之和 =$\frac{p-1}{2}\frac{q-1}{2}$

这里 发现中间用到了奇偶性，毕竟是(-1)的次方，所以会有一点不那么精确得到的感觉

展望

三次互反律，四次互反律，eisenstein互反律,Artin互反律，Langlands纲领

https://zhuanlan.zhihu.com/p/601704520

https://zhuanlan.zhihu.com/p/646169244

lemma 2

n非零整数, p奇素数,$p\not{|}n$,$(x,y)=1$

$p|x^2+ny^2 \leftrightarrow \left(\frac{-n}{p}\right)=1$

证明:

必要性: 这个形式的质因子 满足 -n是p的二次剩余

$x^2+ny^2\equiv 0\pmod{p}$

$p\not{|}y$

$(xy^{-1})^2+n\equiv 0\pmod{p}$

$(xy^{-1})^2\equiv -n\pmod{p}$

充分性: -n是p的二次剩余的p可以表示成$x^2+ny^2$从而多个素因子相乘依然是$x^2+ny^2$

$x^2\equiv -n\pmod{p}$

取$x=x,y=1$即可

延伸 $(x,y)=1,x^2+ny^2$的质因数

$p | x^2+y^2, (x,y)=1 \leftrightarrow \left(\frac{-1}{p}\right)=1 \leftrightarrow p\equiv 1\pmod{4}$

$p | x^2+2y^2, (x,y)=1 \leftrightarrow \left(\frac{-2}{p}\right)=1 \leftrightarrow p\equiv 1\pmod{4}$

$p | x^2+3y^2, (x,y)=1 \leftrightarrow \left(\frac{-3}{p}\right)=1 \leftrightarrow p\equiv 1\pmod{3}$，

$p | x^2+7y^2, (x,y)=1 \leftrightarrow \left(\frac{-7}{p}\right)=1 \leftrightarrow p\equiv 1,2,4\pmod{7}$，

注: 这里上面p可以直接是$n$,因为x取n的倍数，而y不是时，$(x,y)=1$,

Refs

What’s the “best” proof of quadratic reciprocity?