about 2 years ago

前言

今天是Philipsweng的题目。。。第二题考炸了。。

Fenwit

给定一个长度为的向量和一个长度为的向量,定义变换:

次变换后每一项的值模一个数(不一定是质数)。
数据范围:
我们把使得,一次变换可以写成如下形式:

考虑这个东西是可以直接的,中间一个快速幂,所以复杂度就是
中间有点细节:由于异或的需要除以,因此我们事先把,最后再把答案除以即可,中间要用快速乘。
然而还是过不了呀,因为还是太大了,考虑缩小指数规模。
如果,直接用做指数,否则做指数,至于为啥你可以查查,脑补一下就是一个形循环。
这样就能过了。

Stage

一道经典题目,给定二维平面上两个点集中每个点有一个出现概率,求中点构成的凸包能包围住中的点数的期望值,,无三点共线。
考虑补集转化,我们对于每个中的点求出其不在凸包内的概率。
想一下可以发现如果一个点不在凸包内,那么从这个点顺时针做凸包的切线有且仅有一条,因此维护一条切线然后计算一下概率即可,

Alphadog

对于一个字符串,最开始是一个空串,每次加入一个字符并且询问:

定义为以为右端点的最长公共回文子串。
,强制在线。
这题目你搞一个回文树(反正是在线的),因为回文树中的父亲结点是该节点的最长回文后缀,因此对于两个节点的就是其维护一下子树一堆信息和,每次插入时修改并询问一下到根的路径信息即可。
具体做法就是设表示该节点的长度,以及子树大小,那么答案就是:

这个维护的方法很简单,就是记即可。
时间复杂度

← 省选集训:巧克力 TC SRM686 CyclesNumber →
 
comments powered by Disqus