day6

清北学堂--刷题班

讲题

T2
60 -> CRT

sigma(i 1 to n) M/ai*ni(M/ai,ai)*bi

log n

exgcd

ax = 1 %p;
exgcd两两合并
x%a1 = b1
x%a2 = b2
去掉取模
x+k1a1 = b1
x+k2a2 = b
k1a1-k2a2 = b1-b2(有解：gcd(k1,k2)|(b1-b2))
exgcd(a1,-a2,k1,k2)
ax + by = gcd(a,b)
ax + by = c;
x y 乘以c/gcd(a,b)
x%a1a2 = x0
(assert//调试)

T3

二分长度，以一个点为中心，以每个点为中心，往左右找是否相同（hash判断）。 本质不同的回文串个数一共有O（N）个
预处理长相相同的回文串包含多少个好的回文串。
Hash正着求一个数组，反着求一个，若正着与反着hash值相同，则是回文串。枚举长度，通过hash值O(1)判断。再来一个hash数组，记录状态，即这个回文串的好的回文串个数。

字符串

1、hash
将字符串变成整数O（1）
RK-hash：把字符串看作一个base进制的数，对素数p取模
大整数取模

> for （int i=1; i<=len; ++i） {
>     hash[i] = (hash[i-1]*base+s[i])%p; }

hash[i] 字符串到i的哈希值，前缀

base可以取31,131,13131 大于|西格玛|

把a看成1，不能是0,。

p一定是long long 范围的一个素数10^18+9,23,333,333,333,333,333

unsigned long long

多找几个素数

mod p1 == mod p2 <==> mod p1p2

求任一段的h意ash值，

123456 求345的hash值

12345-12000

l...r
hash[r] - hash[l-1]*pow(base,r-l+1) == hash[l...r] pow
可以预处理

求公共前缀
Poj 2758 暴力插入操作，hash+二分
异或，不能取子串的hash

Manachar
首先将所有字符之间添‘#’
以每个点向左向右延伸成为回文串的半径r[i]
S[] = abcbaabcba
R[] = 1131111311

Int mx =
Int id

1、hash

将字符串变成整数O（1） RK-hash：把字符串看作一个base进制的数，对素数p取模 大整数取模

hash[i] 字符串到i的哈希值，前缀 base可以取31,131,13131 大于|西格玛| 把a看成1，不能是0,。 p一定是long

long 范围的一个素数10^18+9,23,333,333,333,333,333 unsigned long long 多找几个素数

mod p1 == mod p2 <==> mod p1p2 求任意一段的hash值， 123456 求345的hash值

12345-12000 l...r hash[r] - hash[l-1]*pow(base,r-l+1) == hash[l...r]
pow 可以预处理

求公共前缀 Poj 2758 暴力插入操作，hash+二分 异或，不能取子串的hash

2.Manachar

O（n）
首先将所有字符之间添‘#’ 以每个点向左向右延伸成为回文串的半径r[i]
S[] = abcbaabcba
R[] = 1131111311

//baoli 
for (int i=1; i<=len; ++i) { 
    r[i] = 1; 
    while (s[i-r[i]] == s[i+r[i]]) r[i]++; 
}

若是aaaaaaaaa...n^2

记录两个变量mx,id; 以id为中心向左向右最大能延伸mx的字符

 for (int i=1; i<=len; ++i) {  
    r[i] = min(r[id-(i-id)],mx-i);  
    while (s[i-r[i]] == s[i+r[i]]) r[i]++;  
    if (i+r[i-1]>mx) {  
        mx = i+r[i]-1； 
       id = i;  
    }  
}

例题：

• bzoj2342 双倍回文
• bzoj3676 会问子串

exkmp

tyvi1068 当前位置：
aabcde
120000 以每个点
//暴力
ababababb
ababb
lcp：最长后缀

p[i] = 0; 
for (int i=1; i<=n; ++i) { 
while (b[i+p[i]==b[p[i]+1]]） p[i]++; } //O(n)

for (int i=1; i<=n; ++i) { 
p[i] = min(mx-i,p[i-id]); 
while (b[i+p[i]==b[p[i]+1]]） p[i]++; 
if（i+p[i]>mx) { 
id = i; 
mx = i+p[i]; 
} }

EXKMP

思路与马拉车相似
要在上次最大匹配的边界内进行扩展
取MIN

trie树

用字符建立节点
开二维数组
第二维记录其儿子
令root=0；

AC自动机

把trie不存在的孩子用fail节点的孩子补出来
求fail指针;要是trie[i][x]存在，则fail[trie[i][x]]=trie[fail[i]][x].
否则，trie[i][x]=trie[fail[i]][x]

段落引用