2017年4月

初等数论 技巧些细

  • 时间:
  • 分类:
  • 评论

大SB·DEL翘课颓到广图什么都不想干，看了一下午不是很熟悉的数论公式。
有些甚至还不会证，先摆上来。
因为没有多少时间，且之后可能几个月没办法继续维护，就先将就放着了。
注意 无行文逻辑。

中国剩余定理 Chinese Remainder Theorem

问题：求同余方程组 $$ 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 $ 而已。

指数循环节(proof under-given)

在模 $ 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 $。无任何互质要求。

二次剩余：欧拉准则 Quadratic Residue: Euler's criterion (proof under-given)

(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} $$

线性基 Linear Basis

  • 时间:
  • 分类:
  • 评论

Linear Basis: A Brief Tutorial (TBC)

线性 <s>Gay</s>

Pre Knowledge

线性代数：矩阵论

Preview & Introduction

线性基本来就是线性代数里面一块基础的内容（所以才叫线性基）。
建立一个独立的专题进行探讨我也是纠结了一会儿。
其概念在线性代数里很重要，而在我打算另写一套线性代数教程的情况下势必会有重复。
然而其在 OI 里面因为异或运算的线性性使得它有更加令人愉悦的用途。
故此我的打算是先完成如此教程，以后作线性代数教程时将另作指向。

本文将重点探讨异或运算与其线性性在线性代数视角的理论及运用，也可作为线性代数学习过程中的一个实例。

Basis: What We Concerned Here in Linear Algebra

线性代数是研究<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 $ 使其成立。

一般的

Field & Operation Axioms

Vector Space

Linear (In)dependent

Linear Combination

Span

Basis

Back to OI: Operation with XOR

XOR: The Definition and Properties

How to Get It: Gaussian Elimination

Problems in OI

SGU 275

题 给出一个集合，问最大异或和。
解 求出线性基后求得异或和即可。

HDU 3949

题 给出一个集合，问第k小异或和。
解 求出线性基后按二进制贡献分类。注意只有当矩阵满秩才会构成零。
码

References

[1]线性基学习笔记|Sengxian's Blog

太懒了所以留个坑督促自己赶紧来写点东西。

替罪羊树 Scapegoat Tree

  • 时间:
  • 分类:
  • 评论

Scapegoat Tree: A Brief Tutorial

重量平衡树：BST

重量平衡树首先是平衡树，其次保证形态的同时优先保证了子树的重量（size）是期望优的。
除了替罪羊树一个例子是Treap。
相关概念可参考[1]。

重量平衡树：The Satisfying Case

Not only what general BST satisifying, but also

  1. maintaining the value set of subtrees
  2. maintaining (almost every) union sets of the info sets of the subtrees on a node
  3. ...

In general BSTs, when we rotate the tree, we need to recalculate the union sets, which costs $ O(n) $ time.

Scapegoat Tree: The Definition

Balanced Factor: $ \alpha $

我们定义一个常量 $ \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。

Keeping Balance: Reconstruction

由于我们不使用旋转操作保证整棵树的平衡，所以我们考虑对所有不平衡的节点，我们暴力重构以其为根的子树。容易发现，当所有节点均为平衡的时，整棵树满足 BST 的定义，也即期望深度为 $ O(\lg n) $。

Erasing Node: Lazy-tagging

对于每次删除节点的操作，我们不直接从原树中删除，而是使用(bool)exist进行标记。当一个点 $ size < total \cdot \alpha $时，也认为其不平衡的，暴力重构。

The Complexity: Time/Space

树的期望深度是 $ \log_{1/\alpha} n $的。所以仍然保证其他操作复杂度仍为对数级别。
使用内存回收的话，空间也是 $ O(n) $ 级别的。

Scapegoat Tree: The Code (Template)

BZOJ 3224(3948 kb 304 ms)

#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;
}

The Advantages

对于一类在线添加节点，而树的形态相对固定，且子树信息难以高效统计（合并，但可以高效添加），替罪羊是一个很好的选择。
例子：后缀平衡树和动态点分治的“重心树”。

The Disadvantages

对于连续序列的操作，替罪羊树显得不在行。
它不支持抽取一段连续的区间并对其进行统计/修改/翻转等旋转平衡树常见操作。

参考 References

[1] 陈立杰.重量平衡树和后缀平衡树在信息学奥赛中的运用.2013年信息学奥林匹克中国国家队候选队员论文.2013

  1. 1
  2. 2
  3. 3