wuvin

出于topcoder对新手太不友好的缘故，前来说一些科学的使用方法 （其实是不想去写题罢了）

首先TC经常是半天登不上去的。（事实无法改变，我试过各国VPN都没有特别好用的，鬼知道他的服务器在哪）

所以

题都看不到做你妹啊！！！

不怕，可以去这里看 MatchOverView (科学上网后很流畅）
看题问题就解决了！
我怎么知道我是对的呢！
题解在这！
如何交题目呢？
诶。。。如果你登不上Arena，那就还有网页版Arena

看dalao们是一套一套刷题的，那我也就制定以下如何做（zuo）题(si)吧。

codeforces round 290-307的div2 E
POI2011
PA2010
deadline: 2016-11-1

2016-10-10

突然发现atcoder好有趣，就是题解搜不到，官方题解是日文的有点不好以外，其他都可以。

10.17

现在的进度：
codeforces round 290-307的div2 E （做了几道，好水啊）
POI2011（OK）
PA2010(BZOJ只有几道，原题没人翻译，弃了)
PA2014(还差一道，难度还没有POI高)
还差cf的一些div2E就可以了。

计划完成的好快，那就加一些吧!
TCO2013 的500（不要问我为什么不做1000，太弱了）

更新后的计划：
codeforces round 290-307的div1 C D (好像这些div1E都是一眼秒呢，没有意思，删了)
TCO2013 的midium
update 10.20
TCO2013 Midium(暂时结坑，自己太弱，完全做不来)

10.24

Finished 完结撒花

11.4

最近发现topcoder 的题目相当有趣啊！说不定下一次来一波SRM也是不错的。算了快联赛了，还是安心刷落谷吧！

update

考完联赛，补完课的我又回来啦！
准备冲省选的只有4个人（我们这一届怎么这么弱，连5个人都没有）

好的，先来一些恢复训练：
POI2013 (卧槽，完全不会做，弃坑)

• splay板子 x1
• LCT板子 x1(不想写，坑掉)
• 凸包板子 x1（这都能调一个上午。。。）
• 半平面交板子 x1
• FFT、NTT、FWT x1
• 点分治 x1(弃坑)
• SAM x1
• 后缀数组 x1

$P \le a$,$a,P$互质 求$x$使得 $a^x \equiv k \pmod P$

解法

令$q=\sqrt{P},x=e *q+ f (f<q)$

$a^f \equiv k * {a^{-qe}} \pmod n$

$f$的取值只有$q$个，$e$的取值也只有$q$个，所以暴力枚举两侧，hash判同即可

来填一下这个坑吧

这两个随机算法还是很好懂的

MR算法 素数判定

首先想必大家都知道费马小定理

如果n是质数，一定有$a^{n-1} \equiv 1 \pmod n$

那么逆否命题正确性与原命题相同，也就是

如果 $a^{n-1} \equiv 1 \pmod n$ , $n$一定为合数

注意：这里没有说这个为1是n是质数，但不为1一定是合数

所以如果要判断n是否是质数只需要选取多个a，再利用快速幂来判定n
如果多个a都说n是不是合数了，那么n基本上就是一个质数了
该测试单次正确的概率是75%所以多测试几次即可。

接下来就是巧妙的rho因数分解了（复杂度O(n^1/4 logn)）

(原文有错，留坑待填)

Description

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。

Input

第一行两个正整数，分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。

Output

一个正整数，表示L的最大值。

Sample Input

7 3
2 4 3 1 3 5 3
< > =

Sample Output

6

HINT

选出的子序列为2 4 3 3 5 3，相邻大小关系分别是< > = < >。

link

好神啊！根本做不来TAT

第一眼 次方级暴力算法
想了一会 好像可以DP
然后发现看错题了。。。。。。（不要问我为什么那么傻
又读了一遍题，发现还是可以DP
想了一个$n^3$的大暴力
又优化了一下成了$n^2logn$
然后又想了一个$n^2$的办法
然后就根本没有想到其他的了。。。
想不出来。。。想不出来。。。只有去看题解了
发现是我dp的状态不对只用保留每个数在最终序列中最靠后的可行位置即可
因为是求最长，可以从后往前证明只用保留最靠后的可行位置不会使答案变小。于是就愉快数据结构优化一下就可以了。

P.S:我原来读错题的版本也是一个DP，只不过原有$i$和

最近学了myy FFT，myy好神啊！ORZORZORZ

先截一张UOJ提交记录

（真不知道jcvb的200ms的FFT是怎么做到的）（人帅常数大）
myy FFT就是把两个FFT装入一个FFT中，最后分离出来。

这样可以减少一半的FFT次数。

假设原有多项式为A和B。C为一个即将FFT的虚数数组

Ci.r=Ai Ci.i=Bi (i为虚数部，r为实数部) $(x,y)$表示实数部为x，虚数系数为y
$F(x)$ 表示将数字带入多项式的结果
设 $x$是单位根的某一个次方

一定带入过$C((nr,mi))$ 和 $C((nr,-mi))$

$(nr,mi)$和$(nr,-mi)$无论多少次方 都满足 实数部相同 虚数部相反

设
$A((nr,mi))=(Ar,Ai)$
$A((nr,-mi))=(Ar,-Ai)$
$B((nr,mi))=(Br,Bi)$
$B((nr,-mi))=(Br,-Bi)$
因为
$C(( nr, mi)) =( Ar - Bi , Ai + Br )$
$C(( nr, -mi ))=( Ar+Bi , -Ai + Br )$
所以可以通过最终结果推出Ar Ai Br Bi就可以求得A和B了

我为什么要写Splay的启发式合并呢？因为这个总体的均摊复杂度是$nlogn$的。

只有一个$log$！

是不是随便怎么合并都是一个$logn$的呢？当然不是。小树往大树先序遍历合并。

为什么要这样呢？一次splay之后可以把一棵树分成两棵树，就可以递归下去合并了，这样越合并树越小，据证明（反正我不会证）这样就可以了！^O^

庆祝自己这次知道五道题怎么做。

庆祝跌rating.庆祝B题看错题。庆祝一个半小时只能写完调完前3题。

现在离结束还有两分钟，过了A\C,B来不及改了，DE来不及写了。真该倒着写的。不过终于可以在3分钟内知道每道题怎么做。相比省选之前只会前四题好多了。

跌吧，跌吧，我不在乎

update

我rating 还涨了85 , 原来是有多弱......

首先回顾了FFT的性质与原理，发现如果单位根w满足一下条件就可以达到FFT的效果。$w^n=1,w^{\frac{n}{2}}=-1$。

所以根据如上理论，NTT的要求w必须是模意义下的原根，这样才可以满足以上要求。而模数mod必须满足$mod=1,2,4,p,2p,p^n$ （p是奇质数）。

原根的判定

在模mod的意义下$x^{\phi(mod)}\equiv 1$，并且不存在比$\phi(mod)$更小的次方满足等于1的条件。