scturtle's 渣代码集散地

不定义函数？那么我们就无法重复利用自身的代码了吗？不，自动机理论中的递归原理的引理告诉我们，一个函数可以得到其自身（读取源文件这种方法无视之），只需要这么做：

A = r'''B = "A = r\'''" + A + "\'''\n" + A
print B'''
B = "A = r\'''" + A + "\'''\n" + A
print B

原理就是分两步，运行时先写下来接下来要做什么（A），然后接下来根据刚才写的就构造出前面和后来都要做些什么，既是整个源程序了。构造过程相反，因为接下来这个过程是确定的，所以先写出接下来，再反填回A。

wr 给的这个链接里的许多程序就是这个原理，虽然比我这个短，但是我这个的好处是接下来这个过程可以随便写，反填时还保持原格式，下面我们利用这个特点实现一个不定义函数的递归程序。

得到程序自身后，当然需要再次运行它，我们利用 exec 这个相当于通用图灵机的函数。因为 exec 默认使用和修改当前的全局和本地变量，所以我们给他加一个虚拟环境 env。这个计算阶乘的程序如下：

A = r'''
B = "A = r\'''" + A + "\'''\n" + A
n = 10
if n == 1:
    ans = 1
else:
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    env = {}
    exec(B,env)
    ans = n * env['ans']
print ans
'''
B = "A = r\'''" + A + "\'''\n" + A
n = 10
if n == 1:
    ans = 1
else:
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    env = {}
    exec(B,env)
    ans = n * env['ans']
print ans

其实在我想出来虚拟一个环境之前，我是实现的下面这个代码。和上面不同的是，由于修改了当前变量，所以无法保存之前的状态（比如 n）。咦？！这不就是尾递归吗？所以就按照尾递归的思路实现了，把 ans 当做变量传下去，如果你做过 SICP 的话，对这种写法应该不陌生。

A = r'''
B = "A = r\'''" + A + "\'''\n" + A
ans = 1
n = 10
if n > 1:
    B = B.replace('ans = '+str(ans),'ans = '+str(ans*n),2)
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    exec(B)
print ans
'''
B = "A = r\'''" + A + "\'''\n" + A
ans = 1
n = 10
if n > 1:
    B = B.replace('ans = '+str(ans),'ans = '+str(ans*n),2)
    B = B.replace('n = '+str(n),'n = '+str(n-1),2)
    exec(B)
print ans

不知道看完本文的你是感到有些蛋疼菊紧呢，还是感到仿佛触碰到了计算机科学的灵魂……

PS: 本文奇葩代码貌似可秒杀多数代码高亮程序，包括 vim，iPython 和本 blog 用的 SyntaxHighlighter，前两者只有一点儿错，可以拷进去看。

同余式及其表示方法是由万能的高斯最先引入的, 定义为 $a$ 和 $b$ 模 $m$ 同余当且仅当 $m \mid (a - b)$. 记做 $a \equiv b\ (mod\ m)$.

最基本的, 同余式满足交换律和传递性.

同余式保持加法和减法:
若 $a\equiv b\ (mod\ m)$ 那么 $a \pm c\equiv b \pm c\ (mod\ m)$

乘法:
若 $a1 \equiv b1\ (mod\ m)$ 且 $a2 \equiv b2\ (mod\ m)$, 那么 $a1 a2 \equiv b1 b2\ (mod\ m)$

在乘法中, 模 $m$ 的倍数相当于零元.
当模 $m$ 为质数 $p$, 而 $k$ 不是零元时, 某定理说一定有乘法逆元 $k^{-1}\epsilon \{1, 2, \cdots, p-1\}$ 的存在, 使:
$k \cdot k^{-1} \equiv 1\ (mod\ p)$

所以当模 $m$ 为质数 $p$, 而 $k$ 不是零元时, $a k \equiv b k\ (mod\ p)$ 两边可以乘以 $k^{-1}$ 消去 $k$ 得到 $a\equiv b\ (mod\ p)$.

若要得到除法, 想要把一边的 $k$ 除到另一边成为 $k^{-1}$ 就得知道乘法逆元的计算方法, 根据费马小定理:
若 $p$ 是质数且 $k$ 不是 $p$ 的倍数. 则有 $k^{p-1} \equiv 1\ (mod\ p)$.
所以 $k^{-1} = k^{p-2}$.

把上面的乘法逆元和除法推广到模为正整数 $n$. 这时和 $n$ 不互质的数相当于零元. 非零元根据某定理亦一定有乘法逆元 $k^{-1}\epsilon \{1, 2, \cdots, p-1\}$ 存在.

同理 $k$ 不是零元时, $a k \equiv b k\ (mod\ n)$ 可消去得到 $a\equiv b\ (mod\ n)$.

欧拉定理是费马小定理的推广:
$n$ 是正整数且 $k$ 互质于 $n$. 则有 $k^{\phi(n)} \equiv 1\ (mod\ n)$.

所以乘法逆元 $k^{-1} = k^{\phi(n)-1}$.

updated at 2013-1-25:

Two ways to influence the modulus:

• Divide all three side by a common divisor:
  $6\equiv 36\ (mod\ 10) \Leftrightarrow 3\equiv 18\ (mod\ 5)$.


• Reduce modulus alone but this is not reversible:
  $7\equiv 13\ (mod\ 6) \Rightarrow 7\equiv 13\ (mod\ 3)$.

updated at 2013-3-31:

$a \equiv b\mod{lcm(p,q)} \quad \Leftrightarrow \quad \begin{equation}\begin{cases} a \equiv b\mod{p} \\\\ a \equiv b\mod{q} \end{cases}\end{equation}$

$a \equiv b\mod{p\ q} \quad \Rightarrow \quad \begin{equation}\begin{cases} a \equiv b\mod{p} \\\\ a \equiv b\mod{q} \end{cases}\end{equation}$ (右边比左边解多)

$$ a^d \equiv 1 \mod {m} $$

设 $\delta$ 为使上成立的最小的 $d$，若 $\delta = \phi(m)$ 则称 $a$ 是模 $m$ 的原根。

对所有 $d$ 有 $\delta \mid d$。$a^0, a^1, \dots, a^{\delta-1}$ 模 $m$ 两两不同余。构成模 $m$ 乘法群（剩余系），阶为 $\delta$。

$ x^a \equiv 1 \mod {p} $ 互不同余的解的个数为 $\gcd(a,\ p-1)$。

整理自algo-class的ppt: note1 note2
参考资料:
Mathematics for Computer Science by Lehman & Leighton
Wikibook on Discrete Probability

样本空间 Ω = "所有可能的情况"
每一种结果 i ∈ Ω, 都有对应的概率 p(i) ≥ 0
样本空间概率和为1:
∑p(i) = 1 for i ∈ Ω
事件是样本空间的子集 S ⊆ Ω
事件的概率的定义:
∑p(i) for i ∈ S

随机变量 X 是一个函数:
X: Ω → ℝ
期望的定义:
随机变量 X 的期望 E[X] = 随机变量 X 的平均值
=∑ X(i)·p(i) for i ∈ Ω
期望的性质:
若 X1,...,Xn 是定义在 Ω 上的随机变量, 则
E[∑Xi] = ∑[E[Xi]]
(即使 Xi 不独立也成立! 但乘法不一样, 见下)

若 X,Y ⊆ Ω 是事件:

那么条件概率"Y发生下X发生的概率"的定义为:
Pr[X|Y] = Pr[X∩Y] / Pr[Y]
事件独立性的定义:
事件 X,Y ⊆ Ω 是独立的 ⇔ Pr[X∩Y] = Pr[X]·Pr[Y]
根据条件概率的定义:
上面那个成立 ⇔ Pr[X|Y] = Pr[X] ⇔ Pr[Y|X] = Pr[Y]
警告: 不要相信直觉...

随机变量的独立性的定义:
定义在 Ω 上的随机变量 A, B 是独立的 ⇔
事件 Pr[A=a], Pr[B=b] 是独立的, 对于所有的 a b
(⇔ Pr[A=a and B=b] = Pr[A=a]·Pr[B=b] )
如果随机变量 A, B 独立才有:
E[A·B] = E[A]·E[B]
警告: 不要相信直觉...相关的变量也可能独立...

引子——括号匹配问题

2n 个'('和')'组成的括号序列, 有多少种合法的组合方法?
把括号从 0 到 2n-1 编号, 合法的序列第 0 个一定是 '(' , 假设第 0 个括号与第 k 个括号匹配, 则序列 [1 ... k-1] 和 [k+1 ... 2n-1] 应也是合法的括号序列, 所以 k 必须是奇数, 设 k=2i+1 , 得公式:

如果换种说法, n 对括号的序列, 可得更简单的公式:

进一步证明

如果 '(' 看做是入栈, ')' 看做是出栈, 则 2n 个括号的合法序列, 一一对应于 2n 步合法的入栈出栈序列.
n 步入栈 n 步出栈的序列总数为 . 对于一个不合法的序列, 一定会在某一步(设为 2i+1 )发现此时遇到的出栈符号数多于入栈符号数, 即遇到了 i 个 '(' 和 i+1 个 ')'. 此时后面还有 n-i 个 '(' 和 n-i-1 个 ')', 如果将后面的 '(' ')' 互换则得到 n-1 步入栈 n+1 步出栈的序列, wikipedia 上说, 两者是一一对应的, 即一个不合法的 n 入 n 出序列(我擦我XE了), 一一对应了一个 n-1 入 n+1 出的序列. 所以可得公式:

化简得方便的计算公式:

应用

有一大票的问题可以归约到卡特兰数上, 看书也经常会看到把这个当做公式用在和式相关的证明中. wikipedia 上说某书列了66个可以归约到卡特兰数的问题(orz). 一般问题要么可以归约到括号匹配问题, 要么可以归约到入栈出栈问题, 比如:

• n+1 个矩阵连乘的括号化方案数, 可以归约到 n 对括号匹配问题, 所以为 Cn
• 所有在 n×n 格点中不越过对角线的单调对角路径的个数, 可以归约到入栈出栈序列问题, 所以为 Cn
• 有 n+1 个叶子的二叉树的个数, 括号匹配, Cn
• 给定 n 个节点，能构成多少种不同的二叉树, 括号匹配, Cn
• 长度 2n 的dyck word的个数, 入栈出栈序列, Cn
• 通过连结顶点(连接线不相交)而将 n+2 边的凸多边形分成三角形的方法个数, 括号匹配, Cn
• n 个长方形填充一个高度为 n 的阶梯状图形的方法个数, 大概是括号匹配, 不明显不好证, Cn

#include <cstdio>
#include <cstdlib>
#include <ctime>

void swap(int &x, int &y) { int t=x; x=y; y=t; }
void check(int t[],int n)
{
    bool res=true;
    for(int i=0;res && i<n-1;i++)
        if(t[i]>t[i+1])
            res=false;
    if(res)
        puts("Yes");
    else
    {
        puts("No");
        for(int i=0;i<n;i++)
            printf("%d ",t[i]);
        puts("");
    }
}

//////////////////////////////////////////////////////

int partation(int a[], int l, int r,int pi)
{
    swap(a[r],a[pi]);
    int p=a[r],here=l,j;
    for(j=l;j<r;j++)
        if(a[j]<p)
            swap(a[here++],a[j]);
    swap(a[here],a[r]);
    return here;
}

void qsort1(int a[], int l, int r)
{
    if(l>=r) return;
    int p=partation(a,l,r,(l+r)/2);
    qsort1(a,l,p-1);
    qsort1(a,p+1,r);
}

//////////////////////////////////////////////////////

void qsort2(int a[],int l,int r)
{
    if(l>=r) return;
    int p=a[l],i=l,j=r+1;
    while(1)
    {
        while(a[++i]<p);
        while(a[--j]>p);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    swap(a[j],a[l]);
    qsort2(a,l,j-1);
    qsort2(a,j+1,r);
}

//////////////////////////////////////////////////////

void qsort3(int a[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=r+1,p=a[(l+r)/2];
    while(1)
    {
        while(a[++i]<p);
        while(a[--j]>p);
        if(i>j) break;
        swap(a[i],a[j]);
    }
    qsort3(a,l,j);
    qsort3(a,i,r);
}

//////////////////////////////////////////////////////

const int n=10000;
int t[n];

int main()
{
    freopen("out","w",stdout);
    srand(time(NULL));
    for(int i=0;i<n;i++)
        t[i]=1+rand()%1000;
    qsort3(t,0,n-1);
    check(t,n);
    return 0;
}