技巧

自然溢出

• 自然溢出不会影响低位数据,所以有的时候你不需要取模,而是一个unsigned.

除法取模

对于式子

细节

• 注意数据类型,例如6*(ll)(1<<30)是要出问题的
• 注意函数在$f(1)$位置的取值,不要忘记初始化

单点$\phi$的求解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ll euler_phi(ll n) {
    ll m = sqrt(n + 0.5);
    ll ans = n;
    for (ll i = 2; i <= m; i++)
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

Divisor

Given $n$ and $m$ ($1 \leq n,m \leq 5 \times 10^4$), please calculate

You are given a string S consisting of only lowercase english letters and some queries.

For each query (l,r,k), please output the starting position of the k-th occurence of the substring SlSl+1…Sr in S.

分析

第一个问题是快速找出所有出现的子串的位置,可以使用后缀数组.这些字串出现在sa的一个连续的区间中.

内容有复制和参考。

这篇文章主要用于记录在探索评测系统Reef期间我所学的东西,以便之后查阅.

Reef预计主要支持远程评测

加一点本地评测…..