牛客暑期多校训练9

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

考虑斐波拉契的循环节,拆模数之后循环节不大,暴力求答案,然后CRT合并

B

$$x=b-y=c·y^{-1}(mod\ p)$$转化成$$y^2-by+c=0(mod\ p)$$,即一般式的二次同余方程

配方后转化成$$x^2=a(mod\ p)$$的经典形式,套模板即可

C

D

折半DP

E

答案随时间递减

考虑将x,y连边后,减少的答案相当于原来包含x,y和另外两个不在同一集合的点

维护每个集合大小和各个集合选2个点的方案数之和即可

F

G

H

I

J

考虑对称轴从下向上移动时,对于每一个矩形的影响是不变(0)-增加-减少-不变(0)的单峰函数,而变化点则是两个边界及中点

将所有边界点和中点存下来并排序,扫一遍维护答案即可