P4213 【模板】杜教筛（Sum）

杜教筛用于在亚线性时间内求出积性函数的前缀和。复杂度 O(n^{\frac{3}{2}})

详见笔记。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 5e6 + 6, Calced = 2e6;
int isnt[N], mu[N], phi[N], prime[N], cnt;
unordered_map<int, int> _phi, _mu;

void sieve() {
    isnt[1] = isnt[0] = true;
    mu[1] = 1; phi[1] = 1;
    for(int i = 2; i <= Calced; i++) {
        if(!isnt[i]) {
            prime[++cnt] = i;
            mu[i] = -1; phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= Calced; j++) {
            isnt[i * prime[j]] = true;
            if(i % prime[j] == 0) { 
                mu[i * prime[j]] = 0;
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            mu[i * prime[j]] = mu[i] * mu[prime[j]];
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for(int i = 1; i <= Calced; i++) {
        mu[i] += mu[i - 1];
        phi[i] += phi[i - 1];
    }
}

int solve_phi(int n) {
    if(n <= Calced) return phi[n];
    if(_phi.count(n)) return _phi[n]; 
    int res = n * (n + 1) / 2;
    for(int l = 2; l <= n; ) {
        int r = min(n / (n / l), n);
        res -= (r - l + 1) * solve_phi(n / l);
        l = r + 1;
    }
    return _phi[n] = res;
}

int solve_mu(int n) {
    if(n <= Calced) return mu[n];
    if(_mu.count(n)) return _mu[n];
    int res = 1;
    for(int l = 2; l <= n; ) {
        int r = min(n / (n / l), n);
        res -= (r - l + 1) * solve_mu(n / l);
        l = r + 1;
    }
    return _mu[n] = res;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    sieve();
    int T = rd();
    while(T--) {
        int n = rd();
        cout << solve_phi(n) << " " << solve_mu(n) << endl;
    }
    return 0;
}

P5357 【模板】AC自动机（二次加强版）

Trie图版。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 2e5 + 6;

struct Edge {
    int to, nxt;
} Edge[N << 1];
int head[N], cnt;
void addEdge(int u, int v) {
    Edge[++cnt].to = v;
    Edge[cnt].nxt = head[u];
    head[u] = cnt;
}

inline int idx(char c) { return c ^ 96; }
queue<int> Q;
class Aho {
public :
    static const int N = ::N;
    int fail[N];

    class Trie {
    public :
        static const int N = ::N;
        int tr[N][27], ed[N], cnt;
        vector<int> end;

        void clear() {
            memset(tr, -1, sizeof tr);
            end.clear();
            ms(ed);
            for(int i = 1; i <= 26; i++) tr[0][i] = 1;
            cnt = 1;
        }

        Trie() {
            clear();
        }

        void insert(char *s) {
            int len = strlen(s + 1), u = 1;
            for(int i = 1; i <= len; i++) {
                int ch = idx(*(++s));
                u = (tr[u][ch] == -1 ? (tr[u][ch] = ++cnt) : tr[u][ch]);
            }
            end.push_back(u);
        }
    } trie;

    void clear() {
        trie.clear();
        ms(fail);
    }

    void build() {
        fail[1] = 0;
        Q.push(1);
        addEdge(0, 1); addEdge(1, 0);
        while(!Q.empty()) {
            int u = Q.front(); Q.pop();
            for(int i = 1; i <= 26; i++) {
                const int v = trie.tr[u][i];
                if(v == -1) {
                    trie.tr[u][i] = trie.tr[fail[u]][i];
                    continue;
                }
                fail[v] = trie.tr[fail[u]][i];
                addEdge(v, fail[v]); addEdge(fail[v], v);
                Q.push(v);
            }
        }
    }

    void match(char *s) {
        int len = strlen(s + 1), u = 1;
        for(int i = 1; i <= len; i++) {
            u = trie.tr[u][idx(*(++s))];
//          d(u);
            ++trie.ed[u];
        }
    }
} ac;

void dfs(int u, int d) {
    for(int i = head[u]; ~i; i = Edge[i].nxt) {
        const int v = Edge[i].to;
        if(v == d) continue;
        dfs(v, u);
        ac.trie.ed[u] += ac.trie.ed[v];
    }
}

const int M = 2e6 + 6;
char str[M], pattern[N];

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd();
    memset(head, -1, sizeof head);
    for(int i = 1; i <= n; i++) {
        scanf("%s", pattern + 1);
        ac.trie.insert(pattern);
    }
    ac.build();
    scanf("%s", str + 1);
    ac.match(str);
    dfs(0, 0);
    for(auto it : ac.trie.end) {
        printf("%d\n", ac.trie.ed[it]);
    }
    return 0;
}

P5610 [Ynoi2013] 大学 & 弱化版 P3987 我永远喜欢珂朵莉~

花神套路题。\bmod 运算近似等价于 \div 2 操作，即至少会让当前数减半。

因为答案为 1

一个小技巧：用并查集维护

LOJ6278 数列分块入门 2

分块套路 1.

CF76A Gift

P5304 [GXOI/GZOI2019]旅行者

CF147B Smile House

P3205 [HNOI2010]合唱队

P3999 [SHOI2013]二重镇

P3990 [SHOI2013]超级跳马

P3377 【模板】左偏树（可并堆）

P3381 【模板】最小费用最大流

P3386 【模板】二分图最大匹配

P4277 河城荷取的烟花

P5459 [BJOI2016]回转寿司

P1456 Monkey King

P1485 火枪打怪 / 【一本通 二分与三分】 手机游戏

二分。因为子弹只会对左方的妖怪造成伤害，因此优先攻击右边的妖怪。

对于一个 p，有固定的 len 使得射击 i 妖怪时， [i-len, i] 是受到的影响妖怪的区间。

考虑如何高效的统计妖怪受到的溅射伤害。

注意到线性运算具有结合律。维护即可。

【一本通 二分与三分】 软件开发

CF1474D - Cleaning

考虑第一个位置，我们只能同时取走位置 [1,2] 以取走 1。

取尽后，第二个位置变成了新的第一个位置。

根据这个方法，如果我们不交换，可以得到最后仅剩 1 堆的石子。 若这堆石子有剩余，则无全部取尽的方法。反之则反。

另：如果交换 [i,i+1] 的顺序，1, 2, ..., i-2 的取法不会有改变

因此我们可以另 s_i 为从前往后取，当 1,2,...,i-1 取尽时，第 i 堆石子剩余的数量。

令 p_i 表示从后往前取，当 i + 1, i + 2, ... n 取尽时，第 i 堆石子剩余的数量。

咕咕咕

P4735 最大异或和

HDU - 4757

P2839 [国家集训队]middle

P3293 [SCOI2016]美味

P4197 Peaks

P4054 [JSOI2009]计数问题

最后修改：2021 年 02 月 16 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏