形式与套路式 划重点！一切莫比乌斯反演题推柿子都等价于以下套路! $$ \begin{aligned} \left[gcd(i,j)=1\right]&\iff\sum_{d\mid gcd(i,j)}\mu(d)\cr \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)]&\iff\sum_{d}\sum_…

核心柿子 我们要求积性函数 $f$ 的前缀和。设： $$S(n)=\sum_{i=1}^{n}f(i)$$ 我们找到另一个积性函数 $g$，则有： $$ g(1)S(n)=\sum_{i=1}^{n}(f * g)(i)-\sum_{i=2}^{n}g(i)\cdot S\left(\left\lfloor\frac{n}{i}\right\rfl…

min25 筛分为两部分。第一部分可以求质数点值的前缀和（例如：$n$ 以内的质数之和），第二部分可以处理积性函数 $f(x)$ 前缀和，要求 $f(p)$ 是一个低阶多项式（如：$f(p)=p^2+p$），且 $f(p^c)$ 可快速求值。 以下介绍均以洛谷模版题为例：洛谷P5325 ：$f(p^k)=p^k(p^k-1)$ 第一部分-求质数点的…

hdu6607 题目大意： $$ \sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)^klcm(i, j)[gcd(i,j)\in prime]\pmod {1e9 + 7} $$ 其中 $n\le {10}^{10},\ k\le 100$ 分析： 方法一： $$ \begin{aligned} f(n,k)&=\s…

矩阵类 构造函数 struct Matrix { int n, m; vector< vector<int> > a; void clear() { vector<int> tmp(m + 1); a.resize(0); for (int i = 0; i <= n; i++) { a.push_back…

行列式求值 struct Matrix { int n, m; vector< vector<int> > a; void clear() { vector<int> tmp(m + 1); a.resize(0); for (int i = 0; i <= n; i++) { a.push_back(tm…

性质 线性基的二进制最高位互不相同 原序列里面的任意一个数都可以由线性基里面的一些数异或得到 线性基里面的任意一些数异或起来都不能得到 $0$ 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的 线性基的基本操作 最大化异或和 P3812 【模板】线性基 题目大意： 给 $n$ 个数，最大化异或和 #include <bit…

Burnside 引理 $$ |X/G|=\frac{1}{|G|}\sum_{g\in G}X^g $$ 其中， $X^g$ 为 $X$ 在 $g$ 作用下的不动点的数量。即满足 $g(x)=x$ 这样的 $x$ 的数量. 文字描述：$X$ 在置换群 $G$ 作用下的等价类总数等于每一个 $g$ 作用于 $X$ 的不动点的算数平均值. 例题 题目…

朴素方法 $n$ 个点 $(x_i,y_i)$ 可以唯一地确定一个多项式 $y = f(x)$。 给定这 $n$ 个点，请你确定这个多项式，并求出 $f(k) \bmod 998244353$ 的值。 #include <bits/stdc++.h> using namespace std; const int P = 99824435…

普通多项式乘法 #include <bits/stdc++.h> using namespace std; #define SZ(o) (int)o.size() namespace FFT { typedef double db; typedef vector<double> vdb; const int N = 3e6 …