杜教筛
谁告诉我这东西怎么翻译成英文啊(躺
照例备份代码
谁告诉我这东西怎么翻译成英文啊(躺
照例备份代码
说不定会再开一个坑呢(躺
备份一下代码
大SB·DEL翘课颓到广图什么都不想干,看了一下午不是很熟悉的数论公式。
有些甚至还不会证,先摆上来。
因为没有多少时间,且之后可能几个月没办法继续维护,就先将就放着了。
注意 无行文逻辑。
问题:求同余方程组 $$ x \equiv a_i \pmod {m_i} \tag{1} \label{1} $$ 的通解,其中 $ (m_i, m_j)=1 $。
其实这并不是一个算法,而只是一个特别巧妙地构造解的技巧而已……思维上很有难度,但一旦作为一个定理证明则特别简单。
Theorem 1 (CRT) 令 $ M = \prod_i m_i, w_i = M / m_i $,且令 $ e_i, f_i \in \mathbb Z_+ $ 满足 $ w_ie_i+m_if_i=(w_i,m_i)=1 $$,则 $$ \eqref{1} $ 的通解为 $$ x equiv sum_i a_ie_iw_i pmod M $$
Proof 考察解之于每一个$ m_i $,注意到每一项除了$ a_ie_iw_i $均因被$ m_i $整除而被约去,而$ w_ie_i+m_if_i=1 $变形即得$ w_ie_i \equiv 1 \pmod {m_i} $,故该通解 satisfying 原题一切方程。Q.E.D.
Mathjax 没有小黑方块真不爽
在 OI 里面的运用的话,也就一个拓欧求各 $ e_i $ 而已。
在模 $ p \in \mathbb P $ 剩余系 $ \mathbb Z/p \mathbb Z $ 下所有数均为该群的生成元。即对$ a \in \mathbb Z/p \mathbb Z $,$ a^i $ 表示之内所有数。
由(Fermat's) $ a^{p-1} \equiv 1 \pmod p $ 可知每 $ p-1 $ 次幂一循环。
拓展由(Euler's)$ a^{\varphi(n)} \equiv 1 \pmod n, (a,n)=1 $给出,当$ a,n $互质时,每$ \varphi(n) $次幂一循环。
更通用情况为$ a^x \equiv a^{x \text{mod} \varphi(n) + \varphi(n)} \pmod n $。无任何互质要求。
(Euler's)
$$ a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod p, & \text{if there is an interger} x \text{such that} x^2 \equiv a \pmod p \\\\ -1 \pmod p, & \text{otherwise} \end{cases} $$
线性 <s>Gay</s>
线性代数:矩阵论
线性基本来就是线性代数里面一块基础的内容(所以才叫线性基)。
建立一个独立的专题进行探讨我也是纠结了一会儿。
其概念在线性代数里很重要,而在我打算另写一套线性代数教程的情况下势必会有重复。
然而其在 OI 里面因为异或运算的线性性使得它有更加令人愉悦的用途。
故此我的打算是先完成如此教程,以后作线性代数教程时将另作指向。
本文将重点探讨异或运算与其线性性在线性代数视角的理论及运用,也可作为线性代数学习过程中的一个实例。
线性代数是研究<s>搞</s>基的代数学。
线性空间(Linear Space)的基底(Basis)的概念,在高中数学学习向量初步的时候其实已经略有涉及。
我们已经知道,平面上任意两个不共线的向量的线性组合可以表示平面任意向量。Namely, 给定
基底向量 $ \mathbf v_0 ,\mathbf v_1 $,则对所有向量 $ \mathbf v = a \mathbf v_0 + b \mathbf v_1 $ 均存在 $ a,b \in \mathbb R $ 使其成立。
一般的
题 给出一个集合,问最大异或和。
解 求出线性基后求得异或和即可。
题 给出一个集合,问第k小异或和。
解 求出线性基后按二进制贡献分类。注意只有当矩阵满秩才会构成零。
码
太懒了所以留个坑督促自己赶紧来写点东西。
重量平衡树首先是平衡树,其次保证形态的同时优先保证了子树的重量(size)是期望优的。
除了替罪羊树一个例子是Treap。
相关概念可参考[1]。
Not only what general BST satisifying, but also
In general BSTs, when we rotate the tree, we need to recalculate the union sets, which costs $ O(n) $ time.
我们定义一个常量 $ \alpha \in (0,1) $ ,$ size(o) $指以$ o $ 为根子树有效结点个数,则称满足 $ size(lc(o)) > size(o) \cdot \alpha \lor size(rc(o)) > size(o) \cdot \alpha $ 的节点是不平衡的。
实现中一般选取alpha = 0.75
。
由于我们不使用旋转操作保证整棵树的平衡,所以我们考虑对所有不平衡的节点,我们暴力重构以其为根的子树。容易发现,当所有节点均为平衡的时,整棵树满足 BST 的定义,也即期望深度为 $ O(\lg n) $。
对于每次删除节点的操作,我们不直接从原树中删除,而是使用(bool)exist
进行标记。当一个点 $ size < total \cdot \alpha $时,也认为其不平衡的,暴力重构。
树的期望深度是 $ \log_{1/\alpha} n $的。所以仍然保证其他操作复杂度仍为对数级别。
使用内存回收的话,空间也是 $ O(n) $ 级别的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T>
inline void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const double alpha = 0.75;
const int maxn = 1e5 + 100;
struct Node
{
int ch[2];
int v, size, total;
bool exist;
} pool[maxn];
int pcnt = 1, tag, root = 0;
int sta[maxn], st = 0;
#define lc(o) (pool[o].ch[0])
#define rc(o) (pool[o].ch[1])
#define v(o) (pool[o].v)
#define size(o) (pool[o].size)
#define total(o) (pool[o].total)
#define exist(o) (pool[o].exist)
inline void maintain(int o)
{
size(o) = size(lc(o)) + size(rc(o)) + exist(o);
total(o) = total(lc(o)) + total(rc(o)) + 1;
}
inline bool check(int o)
{
return (double)total(o) * alpha < (double)total(lc(o)) || (double)total(o) * alpha < (double)total(rc(o));
}
void ins(int &o, int x)
{
if(!o)
{
if(st) o = sta[--st];
else o = pcnt++;
pool[o] = (Node){{0, 0}, x, 1, 1, true};
}
else
{
if(x <= pool[o].v) ins(lc(o), x);
else ins(rc(o), x);
maintain(o); if(check(o)) tag = o;
}
}
int a[maxn], ac = 0;
void deconstruct(int o, bool first = true)
{
if(!o) return;
deconstruct(lc(o), false);
if(exist(o)) a[ac++] = pool[o].v;
deconstruct(rc(o), false);
if(!first) sta[st++] = o;
}
void construct(int &o, int L = 1, int R = ac - 1)
{
if(L > R) return;
int M = (L + R) >> 1;
if(!o && st) o = sta[--st];
else if(!o) o = pcnt++;
pool[o] = (Node){{0, 0}, a[M], 1, 1, true};
construct(lc(o), L, M - 1), construct(rc(o), M + 1, R), maintain(o);
}
void reconstruct(int &o)
{
ac = 1;
deconstruct(o);
construct(o);
}
inline void insert(int x){tag = 0; ins(root, x); if(tag) reconstruct(tag);}
void del(int o, int x)
{
if(!o) return;
if(exist(o) && size(lc(o)) + exist(o) == x)
{
exist(o) = false, maintain(o);
return;
}
if(size(lc(o)) + exist(o) < x)
{
del(rc(o), x - size(lc(o)) - exist(o));
}
else
{
del(lc(o), x);
}
maintain(o);
}
int Rank(int x)
{
int o = root, ans = 1;
while(o)
{
if(v(o) >= x) o = lc(o);
else ans += size(lc(o)) + exist(o), o = rc(o);
}
return ans;
}
int kth(int x)
{
int o = root;
while(o)
{
if(size(lc(o)) + exist(o) == x && exist(o)) return v(o);
if(size(lc(o)) + exist(o) >= x) o = lc(o);
else x -= size(lc(o)) + exist(o), o = rc(o);
}
}
inline void del(int x)
{
del(root, Rank(x));
if((double)size(root) < alpha * (double)total(root)) reconstruct(root);
}
int main()
{
int n; read(n);
while(n--)
{
int opt, x; read(opt, x);
if(opt == 1) insert(x);
else if(opt == 2) del(x);
else if(opt == 3) printf("%d\n", Rank(x));
else if(opt == 4) printf("%d\n", kth(x));
else if(opt == 5) printf("%d\n", kth(Rank(x) - 1));
else printf("%d\n", kth(Rank(x + 1)));
}
return 0;
}
对于一类在线添加节点,而树的形态相对固定,且子树信息难以高效统计(合并,但可以高效添加),替罪羊是一个很好的选择。
例子:后缀平衡树和动态点分治的“重心树”。
对于连续序列的操作,替罪羊树显得不在行。
它不支持抽取一段连续的区间并对其进行统计/修改/翻转等旋转平衡树常见操作。
[1] 陈立杰.重量平衡树和后缀平衡树在信息学奥赛中的运用.2013年信息学奥林匹克中国国家队候选队员论文.2013