0.说明
本文译自Tarjan的论文:
选取了其中的一部分,有删改,以原文为准。
1.简介
在学习全局流分析和程序优化时,如下图论问题自然地浮现出来。设G(V,E,r)是一张流程图(本文中可以简单地代之以‘有向图’——译者注),以r为起点。我们称G中的节点v支配了另一个节点w,如果每一条从r到w的路径都包含了v。如果v支配w,并且w的其他支配点均支配v,我们就称v是w的最近[……]
渺渺苍天,星光烁烁,美丽家园球外乡
Tonelli-Shanks算法是一个求解二次平方根的算法。即,对于奇素数p,和p的一个二次剩余n,求解x^2≡n (mod p)这样的方程。“n是二次剩余”是什么意思呢?就是这个方程有解,如果没解,就叫“二次非剩余”……
关于二次剩余,有一个叫“勒让德符号”(Legendre symbol)的玩意,它能判断对于奇素数p,a是否为p的二次剩余。懒得贴图片,把它写成L(a,p),其定义就是:
L(a,p)≡a^(
(p-1)/2 ) (mod p),这个值有-1,0,1三种可能。如果a不是p的二次剩余,这个值就是-1;如果a是0,这个值就是0;如果a是p的二次剩余,这个值就是1。
这叫做“[……]
首先,让我们忘掉答案可能会非常大,需要模10^9+7这一事实。我们将稍后考虑这一问题,讨论这将对解答造成何种影响。
问题分为两种情况。
听说写退役感言是传统,那我也写一个吧……
似乎很多OIer会对信息学竞赛怀有一种特殊的感情,我可能没那么强烈。NOI之后,我最主要的感受就一条:结束了,终于结束了。
初一最早听说有信息学竞赛的时候,我其实是拒绝的,因为当时我是一个搞数学竞赛的骚年……但还是抱着试一试的心态去了,结果就一发不可收拾,初中是OI数竞一块搞,高中就翘掉数竞全力搞OI,直到现在。
我对于OI的记忆大致分两半:一半是浮躁,一半是干活。
浮躁的自然很爽。
初中被xwy、cjj、xys、sqh等一堆人带着打CS,NOIP前联机大家被专家BOT血虐,怒而上半自动狙+屏幕[……]