C' est La vie

Mod,div运算
总结起来就是mod和div都是先不看符号进行运算，然后mod的符号跟被mod的数一样，div的符号是“同正异负”。

And,or,xor运算
And:(奇偶乘法法则)   对于二进制的每一位and是(1,1)取1,(1,0)取0,(0,1)取0,(0,0)取0;
or:    对于二进制的每一位or是(1,1)取1,(1,0)取1,(0,1)取1,(0,0)取0;
Xor: (奇偶加法法则)

AxorB，就是要么A而不B，要么B而不A T xor F=F xor T=T T xor T=F xor F=F

变成位运算就是不同取1，相同取0 1 xor 0=0 xor 1=1 1 xor 1=0 xor 0=0

还有    A xor B=B xor A [交换率]    A xor B=C <==> A xor C=B <==>C xor B=A
优先级: not>and(∧)>or(∨)

Shr,shl 运算
Shr: 右移N位 m shr n= m div 2^n  (shr 1=div 2)
Shl: 左移N位 m shl n= m*2^n

第一类Stirling数
S[p,k]代表将n个物体排成k个非空的循环排列（就是圆圈）的方法数
S[p,k] =(p-1)*s[p-1,k] + s[p-1,k-1]
初始条件与S(p,k)一样是s(p,0)=0（p>=1）,s(p,p)=1。
证明：把p分两种情况分析：一是自己排成一个圈，有S(p-1,k-1)种；一种是和别人排在一个圈内，共有(p-1)*S(p-1,k)，系数(p-1)是因为p可以排在任何一个人的左边。

第二类Stirling数
S[n,m]代表将一个含有n个不同元素的集合划分成m个不相交的非空子集(盒子不做区分)的不同方案数
S[n,m]=m*S[n-1,m]+S[n-1,m-1]，其中1For i:=1 to n do
For j:=1 to i do
  If j=1 then s[i,j]:=1
  Else s[i,j]:=j*s[i-1,j]+s[i-1,j-1];
(第一类和第二类Stirling数事实上的意义比上面讲到的要丰富，它们是P(n,p)与n^p这两组多项式向量空间的基互相表示的系数)

变形:
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子(vijos1210)
Ans:=s[n,r]*r!    Or    S’[i,j]:=j*(s’[i-1,j]+s’[i-1,j-1]);

Bell数:B_p表示将p个元素的集合划分成一些不可辨别的非空集合的方法数，由第二类Stirling数的定义，显然有：B_p = S(p,0) + S(p,1) + …… + S(p,p)。
还有一个递推式：B_p = ∑C(p-1,i)B_i (0<=i< p)

Catalan数
H (0) = 1
H (n) = H (0) H (n-1) + H (1) H (n-2) + H (2) H (n-3) … + H (n-2) H (1) + H (n-1) H (0)
=> H (n) = (1/ (n+1)) * C (n, 2n)

数字划分模型
*NOIP2001数的划分
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
d[0,0]:=1;
for p:=1 to n do
for i:=p to n do
for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]);
writeln(d[n,k]);
*变形1：考虑顺序
d[ i, j] : = d [ i-k, j-1] (k=1..i)
*变形2：若分解出来的每个数均有一个上限m
d[ i, j] : = d [ i-k, j-1] (k=1..m)

错位排列

递推 d[1] = 0; d[2] = 1; d[n] = (n-1) * (d[n-1] + d[n-2])

排列组合 d[n] = C(n,0)*n!-C(n,1)*(n-1)!+...-...C(n,n)*0!        = ∑(-1)^k*c(n,k)*(n-k)!  (k=0 to n)

错位排列前5项: D[2]=1 d[3]=2 d[4]=9 d[5]=44

Pascal集合运算
+:并 –差(A-B表示属于A但不属于B) *:交 <=:包含于 >=:包含
内文分页： [1] [2]