Lucius7nya

同余问题常用定理证明

发表于 2025-11-06 更新于 2025-07-21

扩展欧几里得算法

扩展欧几里得定理：设和不全为，则存在整数和，使得。

证明：设，求的一组。

欧几里得算法可知，。

即，。

则。

可以通过欧几里得算法递归迭代到时可以得到此时，再利用上面推出的与的关系进一步代入计算，得到的一组解。

利用归纳法，最后解的大小满足：。

int exgcd (int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd (b, a % b, y, x);

    y -= (a / b) * x;

    return d;
}

欧拉定理 & 费马小定理

欧拉定理：若，则。

证明：设是模的缩系，因为，所以也是模的缩系。

即。

根据缩系性质，可约去，即得。

费马小定理：若为素数，则。

证明：当为素数，由于，带入欧拉定理可立即得到费马小定理。

线性同余方程

设，则一次同余方程：，有解的充要条件是。

设同余方程有解，则，从而，但，故。

反过来，若，则同余方程与同解，任取模的一个完系，因，也是模的完系，所以同余方程存在整数解，且形成模的一个同余类。但时，原同余方程（模）恰有个解。

int x, y;
int d = exgcd (a, p, x, y);

if (b % d) {
    res = -1;
} else {
    x *= (b / d);
    res = (x % (p / d) + (p / d)) % (p / d);
}

中国剩余定理

中国剩余定理：设是两两互素的正整数，则对于任意整数，一次同余方程组必有解，且全部解是模的一个同余类。确切地说，同余方程组的解是。

其中及由条件决定。因为，故有整数，使得。对，有，因此数，满足：（对）。

易于验证，上面的解的”叠加“ 满足同余方程组的解。

另一方面，如果都是同余方程组的解，则。由两两互素知，，因此同余方程组的解是模的一个同余类。

线性同余方程组

模数互质，使用中国剩余定理。

vector <int> A(n), B(n);
LL M = 1;
for (int i = 0; i < n; i ++ ) {
    cin >> A[i] >> B[i];
    M *= A[i];
}

LL res = 0;
for (int i = 0; i < n; i ++ ) {
    LL Mi = M / A[i];
    LL ti, x;
    exgcd (Mi, A[i], ti, x);
    res += B[i] * Mi * ti;
}

cout << (res % M + M) % M << "\n";

在模数不互质的情况下，设其中两个方程分别是。转化为不定方程：，其中是整数，则有。由裴蜀定理，当不能被整除时，无解；否则，扩展欧几里得定理得到一组可行解，则这两个方程组的解是，其中。多个方程两两合并。

LL res = 0, m1, a1;
cin >> m1 >> a1;

for (int i = 0; i < n - 1; i ++ ) {
    LL m2, a2;
    cin >> m2 >> a2;

    LL k1, k2;
    LL d = exgcd (m1, m2, k1, k2);

    if ((a2 - a1) % d) {
        res = -1;
    }

    k1 *= (a2 - a1) / d;
    k1 = (k1 % (m2 / d) + (m2 / d)) % (m2 / d);

    LL m = abs (m1 / d * m2);
    a1 = k1 * m1 + a1;
    m1 = m;
}

if (res != -1) {
    res = (a1 % m1 + m1) % m1;
}

cout << res << "\n";

循环引理 (Cycle Lemma) —— 原理与竞赛应用

发表于 2025-11-06 更新于 2025-10-06

generated by chatgpt 5 thinking

核心原理简述

名称：循环引理（Cycle Lemma），又称 Dvoretzky–Motzkin 引理，是组合计数中的经典工具。
地位：该引理地位重要，常用于解决前缀和约束类的问题，如合法括号串计数、Ballot 投票问题、Dyck 路径等。
用途：针对含“+1/–1”步长的序列，统计循环移位后前缀和保持非负（或正）的情况。例如，判断一个环形序列从哪个起点展开能形成合法序列。
核心原理：设数列的前缀和总和为正整数，则恰有个循环移位使得所有前缀和始终为正。直观上，相当于将序列沿环反复“滑动”，正好种滑动能保持前缀优势。
结构公式：若序列中有个 “+1” 和个 “–1”（记作有个 X 和个 Y，且），那么正有个循环移位使得任意前缀中 X 的数量恒大于 Y 的数量。这个量度了序列总和的大小。

引导式构建

现象：观察实际问题时，常遇到“轮换序列仍满足某条件”的情况。例如，在括号串计数或投票序列中发现，序列的循环移位中，满足前缀和非负的数量似乎与总和存在简单关系。
猜想：基于观察猜测：如果序列的总和为，那么恰好有个循环移位使得前缀和非负。也就是，总和越大，可行的循环起点数量越多。
验证：通过小样本测试验证猜想。例如，对于序列 (+1, -1, +1, +1, -1)（总和=+1），枚举所有环形旋转后发现恰有 1 个循环移位使得所有前缀和非负。进一步用“删除相邻 +1–1 对”或“最小前缀和位置”方法可证明一般情况：将序列按环连起来，不断配对去掉一对 (+1, –1)，最终余下正步的数量即为可行起点数。
定理：归纳得出正式结论——循环引理：对任意总和为正的序列，总和数即为循环有效移位数。这一结论可以视为 Ballot 定理和 Catalan 数公式的“环形”推广。
迁移：将此思路推广到类似问题，如将括号序列看作 +1/–1 序列加一额外步长、或将多种字符映射成数值后应用引理。还可以推广到Raney 引理（Raney Lemma）：特殊地，当总和为 1 时，恰有 1 个循环移位有效；该情况常用于直接构造 Catalan 数等。

典型题型与变式归纳

括号序列计数（Catalan 相关）：合法括号串可以视为步长序列（“(”记 +1，“)”记 –1），要求前缀和非负且最终和为 0。循环引理证明当插入一额外“(”后（总和为 +1）恰有 1 个循环移位满足条件，从而导出 Catalan 数公式。类似地，可解决括号串的轮换匹配次数或生成题。
投票/随机游走问题：Bertrand 投票问题（候选人 A 票数，B 票数，），计算 A 始终领先的概率。循环引理给出当循环投票顺序总差为时，恰有种循环排列保持 A 永远领先，从而得到概率。更多随机游走、步长问题都可类比此法。
循环移位匹配：字符串或序列的循环移位中寻找满足特定性质的起点。例如，寻找使前缀和达到最小值的下一个位置作为有效起点（最小表示首次走完所有“–1”）。应用循环引理可以计数循环中多少起点合法，或者直接构造这样的位置。典型题目如给定序列求最大合法轮换次数、最小字典序轮换等。
路径/格点计数：在网格路径或山峰序列等计数问题中，常需保证路径不下穿或前缀高度非负。将路径的上升/下降看作 +1/–1，总和为时，循环引理告诉我们有个环形起点对应满足条件的路径，进而归纳出计数公式。

真实竞赛题示例

洛谷 P6672（清华集训 2016）：题意将若干特殊牌和普通牌安排，要求每段前缀和非负。分析中将特殊牌取值，普通牌记作，于是原始序列和为 0，且要求所有前缀和。)。此时向前插入一个额外的并将所有数取反，序列总和变为 +1，满足 Raney/循环引理条件。由引理知恰有 1 个循环移位使得前缀和非负，对应原序列只有 1 种合法安排方式。因此通过确定该循环起点位置，可以得到最终答案。
提示：类似地，任何合法括号串轮换也满足循环引理的结论：如一个长度为的括号串，如果按环旋转，其合法前缀和次数等于序列中净步长的一半。利用这一思想，可以直接枚举旋转起点或计数旋转合法的种类。

易错点与实用建议

符号与方向：注意循环引理要求总和为正（）。如果序列总和为非正，原引理不直接适用，此时需对序列进行适当变换（如添加额外元素或正负转换）后再用引理。
严格与非严格：使用时要分清 “前缀和严格为正” 还是 “非负” 的要求，必要时可对序列加一位正值（如在开头加一个 +1）来转换条件。
最小前缀位置：寻找循环起点的常用技巧是找到前缀和的最小值位置（加一即为起点）。实现时注意序列首尾连通性，细心处理下标和模运算。
边界情况：当序列中“+1”“–1”数量差为 1 或更大时，对应可行起点数量为差值。若差为 0（和为 0），则没有正前缀的循环移位。不要将求解公式机械应用在和为 0 的情形。
应用建议：比赛中遇到前缀和类轮换问题，第一时间判断序列总和，并尝试将问题转化为满足循环引理条件的形式；然后直接使用“总和 = 有效轮换数”的结论。记忆合适的变换技巧（加元素、正负取反等）和典型例子有助快速建模。

数据结构

发表于 2025-11-06

[TOC]

空间换时间

树状数组

修改：单点加。查询：区间和。

询问中的逆序对的个数。

修改：区间加减；查询：单点的值。

线段树

修改：区间加。查询：区间和。

修改：区间乘、区间加。查询：区间和。

查询：区间中有多少个不同的数。

修改：区间加。查询：区间平均值、区间方差。

修改：单点赋值。查询：区间最大字段和。

修改：区间开平方。查询：区间和。

修改：区间或。查询：最大字段和。

修改：区间取模，单点赋值。查询：区间和。

templates

发表于 2025-07-25 更新于 2025-11-10

[TOC]

list

std::list<int> list;
list.push_front(0);
std::vector<std::list<int>::iterator> it(N);
it[0] = list.begin();
for (int i = 1; i < N; i++) {
    int k, p;
    std::cin >> k >> p;
    k--;
    if (p == 0) {
        it[i] = list.insert(it[k], i);
    } else {
        it[i] = list.insert(std::next(it[k]), i);
    }
}

int M;
std::cin >> M;

std::vector<bool> erased(N);

while (M--) {
    int x;
    std::cin >> x;
    x--;
    if (!erased[x]) {
        list.erase(it[x]);
        erased[x] = true;
    }
}

for (int x : list) {
    std::cout << x + 1 << " ";
}

DSU

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

partition_point

二分查找后继：

int ans = *std::ranges::partition_point(std::ranges::iota_view(0, int(1E9) + 1), 
        [&](int k) {
            int L = 0, R = 0;
            for (int i = 0; i < n; i++) {
                L -= k;
                R += k;
                L = std::max(L, l[i]);
                R = std::min(R, r[i]);
                if (L > R) {
                    return true;
                }
            }
            return false;
        });

二分查找：FFFFFTTTTTT

前驱（第一个T）：

int lo = 1, hi = 1E9;
while (lo < hi) {
    int m = (lo + hi + 1) / 2;
    if (check(m)) {
        lo = m;
    } else {
        hi = m - 1;
    }
}
std::cout << lo << "\n";

后继（最大可行值）：
TTTTFFFFF（最后一个 T）：

int lo = 1, hi = 1E9;
while (lo < hi) {
    int m = (lo + hi) / 2;
    if (check(m)) {
        hi = m;
    } else {
        lo = m + 1;
    }
}
std::cout << lo << "\n";

partial_sum

前缀和：

1	std::partial_sum(A.begin(), A.end(), prefix.begin() + 1);

前缀异或和：

1	std::partial_sum(A.begin(), A.end(), prefix.begin() + 1, [](int a, int b) { return a ^ b; });

后缀和：

1	std::partial_sum(A.rbegin(), A.rend(), suffix.rbegin() + 1);

int128

std::ostream &operator<<(std::ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    std::string s;
    while (n > 0) {
        s += char('0' + n % 10);
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

随机数

1	std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

Y conbinator + lambda

bfs + dfs（找环）：

int n, a, b;
std::cin >> n >> a >> b;
a--, b--;

std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

auto bfs = [&](int s) {
    std::vector<int> dis(n, -1);
    dis[s] = 0;
    std::queue<int> q;
    q.push(s);

    while (!q.empty()) {
        auto x = q.front();
        q.pop();

        for (auto y : adj[x]) {
            if (dis[y] == -1) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
    return dis;
};

auto dis = bfs(b);

int u = -1;
std::vector<int> vis(n);
std::vector<int> par(n), dep(n);
auto dfs = [&](auto self, int x) -> void {
    vis[x] = true;

    for (auto y : adj[x]) {
        if (!vis[y]) {
            par[y] = x;
            dep[y] = dep[x] + 1;
            self(self, y);
        } else if (dep[y] < dep[x] - 1) {
            for (int i = x; ; i = par[i]) {
                if (u == -1 || dis[i] < dis[u]) {
                    u = i;
                }
                
                if (i == y) {
                    break;
                }
            }
        }
    }
};
dfs(dfs, 0);

if (bfs(u)[a] > dis[u]) {
    std::cout << "YES\n";
} else {
    std::cout << "NO\n";
}

data structure

fenwick:

0base，add(i, a), sum(i), rangeSum(l, r)

select(x)：前缀和不超过 x 的最大位置。

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

SegmentTree:

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }

    void rangeOr(int p, int l, int r, int x, int y, int v) {
    	if (l >= y || r <= x) {
    		return;
    	}

    	if ((info[p].sumAnd & v) == v) {
    		return;
    	}

    	if (r - l == 1) {
    		int nv = (info[p].sumAnd | v);
    		info[p] = {nv, nv, std::max(0, nv), std::max(0, nv), std::max(0, nv)};
    		return;
    	}

    	int m = (l + r) / 2;
    	rangeOr(2 * p, l, m, x, y, v);
    	rangeOr(2 * p + 1, m, r, x, y, v);
    	pull(p);
    }

    void rangeOr(int l, int r, int v) {
    	rangeOr(1, 0, n, l, r, v);
    }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};

constexpr i128 inf = 4E32 + 1;

struct Info {
	i128 sum = 0;
	int sumAnd = ~0;
	i128 maxSub = -inf;
	i128 pre = -inf;
	i128 suf = -inf;
};

Info operator+ (const Info &a, const Info &b) {
	Info c;
	c.sum = a.sum + b.sum;
	c.sumAnd = a.sumAnd & b.sumAnd;
	c.maxSub = std::max({a.suf + b.pre, a.maxSub, b.maxSub});
	c.pre = std::max(a.pre, a.sum + b.pre);
	c.suf = std::max(b.suf, a.suf + b.sum);
	return c;
}

LazySegmentTree：

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
};

struct Tag {
    i64 add = 0;
    void apply(const Tag &t) & {
        add += t.add;
    }
};

struct Info {
    i64 sum = 0;
    int len = 0;
    void apply(const Tag &t) & {
        sum += t.add * len;
    }
};

Info operator+(const Info &a, const Info &b) {
    return {a.sum + b.sum, a.len + b.len};
}

离散化：

std::vector<int> a(n);
for (int i = 0; i < n; i++) {
	std::cin >> a[i];
}

std::vector<int> v;
for (int i = 0; i < n; i++) {
	v.push_back(a[i]);
}

std::sort(v.begin(), v.end());

for (int i = 0; i < n; i++) {
	a[i] = std::lower_bound(v.begin(), v.end(), a[i]) - v.begin();
}

双指针

for (int x = 0, y = -1; x <= n; x++) {
        if (x < n && s[x] == 'A') {
            ans++;
        } else {
            min = std::min(min, x - y - 1);
            y = x;
        }
    }

dijkstra

std::vector<std::vector<std::pair<int, i64>>> g(n);
   for (int i = 0; i < m; i++) {
       int u, v;
       i64 w;
       std::cin >> u >> v >> w;
       u--;
       v--;
       g[u].push_back({v, w});
       g[v].push_back({u, w});
   }

   
   std::vector<i64> dis(n, INF);
   std::priority_queue<std::pair<i64,int>, std::vector<std::pair<i64,int>>, std::greater<std::pair<i64,int>>> pq;

   pq.emplace(0, T);
dis[T] = 0;
   while (!pq.empty()) {
       i64 d = pq.top().first;
       int u = pq.top().second;
       pq.pop();
       if (d != dis[u]) {
       	continue;
       }
       for (int i = 0; i < g[u].size(); i++) {
           int v = g[u][i].first;
           i64 w = g[u][i].second;
           if (dis[v] > d + w) {
               dis[v] = d + w;
               pq.emplace(dis[v], v);
           }
       }
   }

dijkstra:

#include <bits/stdc++.h>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, t;
	std::cin >> n >> t;

	std::vector<std::vector<std::pair<int, int>>> adj(n);
	for (int i = 0; i < t; i++) {
		int m;
		std::cin >> m;

		for (int j = 0; j < m; j++) {
			int u, v;
			std::cin >> u >> v;
			u--;
			v--;
			adj[u].emplace_back(v, i);
			adj[v].emplace_back(u, i);
		}
	}

	int k;
	std::cin >> k;

	std::vector<std::vector<int>> pos(t);
	for (int i = 0; i < k; i++) {
		int a;
		std::cin >> a;
		a--;
		pos[a].push_back(i);
	}

	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> q;
	q.emplace(0, 0);
	std::vector<int> dis(n, -1);

	while (!q.empty()) {
		auto [d, x] = q.top();
		q.pop();

		if (dis[x] != -1) {
			continue;
		}
		dis[x] = d;

		for (auto [y, i] : adj[x]) {
			auto it = std::lower_bound(pos[i].begin(), pos[i].end(), d);
			if (it != pos[i].end()) {
				q.emplace(*it + 1, y);
			}
		}
	}

	std::cout << dis[n - 1] << "\n";

	return 0;
}

trie 树

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E6 + 10;

int tot = 1;
int trie[N][26];
int cnt[N];


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<std::string> s(n);
	i64 ans = 0;
	for (int i = 0; i < n; i++) {
		std::cin >> s[i];
		ans += s[i].size();

		int p = 1;
		for (auto c : s[i]) {
			int &q = trie[p][c - 'a'];
			if (!q) {
				q = ++tot;
			}
			p = q;
			cnt[p] += 1;
		}
	}

	ans *= 2 * n;
	for (int i = 0; i < n; i++) {
		std::reverse(s[i].begin(), s[i].end());

		int p = 1;
		for (auto c : s[i]) {
			int &q = trie[p][c - 'a'];
			if (!q) {
				break;
			}
			p = q;
			ans -= 2 * cnt[p];
		}
	}

	std::cout << ans << "\n";

	return 0;
}

公式

平方和：

$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

组合数：

/**   组合数（小范围预处理，逆元+杨辉三角）
 *    2024-03-14: https://qoj.ac/submission/353877
 *    2023-10-06: https://qoj.ac/submission/203196
**/
constexpr int P = 1000000007;
constexpr int L = 10000;

int fac[L + 1], invfac[L + 1];
int sumbinom[L + 1][7];

int binom(int n, int m) {
    if (n < m || m < 0) {
        return 0;
    }
    return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
}

int power(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % P) {
        if (b % 2) {
            res = 1LL * res * a % P;
        }
    }
    return res;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= L; i++) {
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
    invfac[L] = power(fac[L], P - 2);
    for (int i = L; i; i--) {
        invfac[i - 1] = 1LL * invfac[i] * i % P;
    }

    sumbinom[0][0] = 1;
    for (int i = 1; i <= L; i++) {
        for (int j = 0; j < 7; j++) {
            sumbinom[i][j] = (sumbinom[i - 1][j] + sumbinom[i - 1][(j + 6) % 7]) % P;
        }
    }
}