statement:https://www.jisuanke.com/contest/5529
赛中过题: A C F

M. Kill the tree

给一棵树，求每棵子树的重心.
考虑从子树的重心转移到根的重心，直接暴力往上跳.
由于路径不相交，这样做的复杂度为

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef long long ll;
#define empb emplace_back
#define sz(x) (int)(x).size()
const int N = 2e5 + 7;
VI E[N];
int ans[N], fa[N], sz[N];
void dfs(int u, int f){
    fa[u] = f;
    ans[u] = u;
    sz[u] = 1;
    for(auto &v : E[u]){
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    for(auto &v : E[u]){
        if(v == f) continue;
        int t = ans[v];
        while(sz[t] * 2 < sz[u]) t = fa[t];
        if(sz[t] < sz[ans[u]]) ans[u] = t;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for(int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        E[u].empb(v);
        E[v].empb(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++){
        if(sz[ans[i]] * 2 == sz[i]) {
            int a1 = ans[i], a2 = fa[ans[i]];
            if(a1 > a2) swap(a1, a2);
            cout << a1 << ' ' << a2 << '\n';
        } else cout << ans[i] << '\n';
    }
    return 0;
}

L.Loli, Yen-Jen, and a cool problem

广义后缀自动机裸题(据说bfs建广义后缀自动机的link转移较少).

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef long long ll;
#define empb emplace_back
#define SZ(x) (int)(x).size()
const int N = 3e5 + 7;

char s[N];
int n, q;
struct SAM {
    static const int M = N << 1;
    int nxt[M][26], len[M], fa[M], tot, last;
    int newnode(int l = 0) {
        memcpy(nxt[++tot], nxt[l], sizeof nxt[0]);
        return tot;
    }
    void init() {
        tot = 0; len[0] = -1;
        last = newnode();
    }
    int extend(int p, int ch, int idx) {
        int f = !!nxt[p][ch]; // f == 1 for exSAM
        int np = f ? nxt[p][ch] : newnode();
        if(!f) len[np] = len[p] + 1;
        for(; !f && p && !nxt[p][ch]; p = fa[p]) nxt[p][ch] = np;
        if(!p) return fa[np] = 1, np;
        int q = nxt[p][ch];
        if(len[p] + 1 == len[q]) {
            if(!f) fa[np] = q;
        } else {
            int nq = newnode(q);
            len[nq] = len[p] + 1;
            fa[nq] = fa[q];
            fa[np] = fa[q] = nq;
            for(; nxt[p][ch] == q; p = fa[p]) nxt[p][ch] = nq;
            if(f) np = nq;
        }
        return np;
    }
    int c[N], topo[M];
    void toposort(int n) {
        memset(c + 1, 0, tot * 4);
        for(int i = 1; i <= tot; i++) c[len[i]]++;
        for(int i = 1; i <= n; i++) c[i] += c[i - 1];
        for(int i = 1; i <= tot; i++) topo[c[len[i]]--] = i;
    }
    int anc[M][20], w[M];
    void build() {
        toposort(n);
        for(int i = tot; i; i--) {
            w[fa[topo[i]]] += w[topo[i]];
        }
        for(int i = 1; i <= tot; i++) anc[i][0] = fa[i];
        for(int i = 1; i < 20; i++)
            for(int j = 1; j <= tot; j++)
                anc[j][i] = anc[anc[j][i-1]][i-1];
    }
    int query(int u, int l) {
        for(int i = 19; ~i; i--)
            if(len[anc[u][i]] >= l)
                u = anc[u][i];
        return w[u];
    }
} sam;


vector<int> E[N];

int pos[N];
void dfs(int u, int l) {
    sam.w[pos[u]=l=sam.extend(l,s[u]-'A',u)]++;
    for(auto &v : E[u])
        dfs(v, l);
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    sam.init();
    cin >> n >> q >> s + 1;
    for(int i = 2, f; i <= n; i++)
        cin >> f, E[f].empb(i);
    dfs(1, 1);
    sam.build();
    while(q--) {
        int x, l; cin >> x >> l;
        cout << sam.query(pos[x], l) << '\n';
    }
    return 0;
}

E.Multiply

大数分解.

#include<bits/stdc++.h>
using namespace std;
typedef long double ldb;
typedef int64_t ll;
typedef uint64_t ull;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const ldb eps = 1e-8;
ull mul_mod(ull a, ull b, ull m) {
    if(a >= m) a %= m; if(b >= m) b %= m;
    ull res = a*b - ull((ldb)a*b/m+eps)*m;
    return ll(res) < 0 ? res + m : res;
    return (__int128) a * b % m;
}
ull power_mod(ull a, ull b, ull m) {
    ull res = 1;
    for(; b; b >>= 1, a = mul_mod(a, a, m))
        if(b & 1) res = mul_mod(res, a, m);
    return res;
}
bool miller_robin(ull a, ull n) {
    if(a >= n) return 1;
    ull s = __builtin_ctz(n - 1), i = 0, d = n >> s;
    ull t = power_mod(a, d, n);
    while(t != 1 && t != n - 1 && i < s)
        t = mul_mod(t, t, n), i++;
    return t == n - 1 || !i;
}

bool isprime(ull n) {
    if(n <= 1) return false;
    if(n % 6 % 4 != 1) return n < 4;
    static vector<ull> t = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for(auto &e : t) if(!miller_robin(e, n)) return false;
    return true;
}
mt19937_64 gen(time(0));
vector<ull> pfactor(ull n) {
    if(n == 1) return {};
    if(isprime(n)) return {n};
    while(1) {
        ull c = gen() % (n - 1) + 1;
        auto f = [n,c](ull x) { return (mul_mod(x,x,n)+c)%n;};
        ull x = gen() % n, y = f(x);
        while(x != y) {
            ull d = __gcd(x - y + n, n);
            if(d != 1) {
                auto l = pfactor(d), r = pfactor(n / d);
                l.insert(l.end(), all(r));
                return l;
            }
            x = f(x); y = f(f(y));
        }
    }
    assert(false);
}

ull calc(const vector<ull>&a, ull y, ull p) {
    ull res = 0;
    while(y /= p) res += y;
    for(int i = 0; i < sz(a); i++) {
        ull t = a[i];
        while(t /= p) res -= t;
    }
    return res;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        ull x, y; cin >> x >> y;
        vector<ull> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
        ull res = LLONG_MAX;
        auto px = pfactor(x);
        sort(all(px));
        for(int i = 0, j = 0; i < sz(px); i = j) {
            while(j < sz(px) && px[j] == px[i]) j++;
            ull num = j - i;
            ull allp = calc(a, y, px[i]);
            res = min(res, allp / num);
        }
        cout << res << '\n';
    }
    return 0;
}

H.Yuuki and a problem

给一个序列,有次操作,
1.
2.询问区间最小不能用子集和表示出来的数.

结论：若能表示出之间的所有数,那么能表示出中的所有数.
注意到这个递增过程类似斐波那契数列，因此，我们可以用线段树树套树状数组来维护二维区间和(如果没有修改操作，可以用可持久化线段树).
总时间复杂度为.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1 << 18 | 7;
const int m = 2e5;
int root[N], a[N], ch[N*80][2], n, q, tot;
ll val[N*80];
void init() { tot = 0;}
int newnode() {
    val[++tot] = 0;
    memset(ch[tot], 0, sizeof ch[0]);
    return tot;
}
void update(int x, int v, int &o, int l, int r){
    if(!o) o = newnode();
    val[o] += v;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(mid >= x) update(x, v, ch[o][0], l, mid);
    else update(x, v, ch[o][1], mid + 1, r);
}
ll query(int ql, int qr, int o, int l, int r){
    if(!o || ql <= l && r <= qr) return val[o];
    ll res = 0;
    int mid = (l + r) >> 1;
    if(ql <= mid) res += query(ql, qr, ch[o][0], l, mid);
    if(qr > mid) res += query(ql, qr, ch[o][1], mid + 1, r);
    return res;
}
void update(int x, int y, int v) {
    for(; x <= n; x += x&-x)
        update(y, v, root[x], 1, m);
}
ll query(int x, int y, int ql, int qr){
    if(ql > qr) return 0;
    ll res = 0;
    while(x != y) {
        if(x > y) res -= query(ql, qr, root[x], 1, m), x -= x&-x;
        else res += query(ql, qr, root[y], 1, m), y -= y&-y;
    }
    return res;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    init();
    cin >> n >> q;
    for(int i = 1; i <= n; i++) root[i] = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i], a[i]);
    }
    while(q--) {
        int op; cin >> op;
        if(op == 1) {
            int x, y; cin >> x >> y;
            update(x, a[x], -a[x]); a[x] = y;
            update(x, a[x], a[x]);
        } else {
            int l, r; cin >> l >> r; l--;
            ll x = -1, y = 0;
            while(1) {
                ll dt = query(l, r, min(x+2ll,(ll)m+1), min(y+1ll,(ll)m));
                if(!dt) break;
                x = y, y += dt;
            }
            cout << y + 1 << '\n';
        }
    }
    return 0;
}