文章来源: http://thunderfyc.wordpress.com.cn
递推
f(x) = f(x-1)+f(x-2)
M = ((0,1),(1,1))
((f(x)), (f(x+1))) * M = ((f(x+1)), (f(x+2)))
((f(x)), (f(x+1))) = ((f(1)), (f(2)))*M^(x-1)
集合划分
n个元素划分到k个集合里
f(n,k) = f(n-1, k-1) + k*f(n-1, k)
n-1个元素放在k-1个集合里 剩下一个单独成集合
或者n-1个元素在k个集合里 剩下一个放置在其中任何一个
错装信封
第i封信不在第i个信封里
假设i在n上 n在i上 剩下n-2个错排 所以有f(n-2)*(n-1)个 i枚举从1到n
假设i不在n上 n在i上 那么去掉n后 n-1个位置对应n-1个数的错排(i考虑为n) 那么有f(n-1)*(n-1)个
f(n) = (f(n-1)+f(n-2))*(n-1)
数论
gcd(a, b) = gcd(b, a mod b)
互素的数的个数
Phi(n) = n(1-1/p1)(1-1/p2)…(1-1/pi)
a^b mod n
b的二进制表示<bk,bk-1,…,b0>
从左到右 d = (d*d) mod n 如果bi=1 d = (d*a) mod n
高精度
排列组合
求排列为第几位
从第一个位置到最后一个 求比当前位置的数更小的数且不和前面相同的可能数 累加
例如 13245 0*4! + 1*3! + 0*2! + 0*1! + 0 = 6 (12345 12354 12435 12453 12534 12543 13245)
41352 3*4! + 0*3! + 1*2! + 1*1! = 75
求某位排列
从第一位开始确定 用x!的倍数来确定是在前面未出现的数中排列第几的数
求后继
找到一个一直延伸到末尾的递减序列 然后将前一个值和递减数列中恰大于它的值互换后 将递减序列排序为递增
解方程
Newton迭代
求导之后 作切线 得到和x轴交点作为新的x 求导 作切线 不断逼近
计算函数解析式
Lagrange插值公式
已知n个点坐标 求过这些点的方程
f(x) = sigma(f(ai) Pi(x-aj[j<>i])/Pi(ai-aj[j<>i]))
不定方程
Euclid
gcd(a, b) = ax + by 有解
(d’,x’,y’) = ext_gcd(b, a mod b) (d,x,y) = (d’, y’, x’-[a/b]y’)
Pythagoras
a^2+b^2=c^2
假设 x = a/c; y = b/c;
x^2+y^2=1
y^2=(1-x)(1+x)=> y/(1+x) = (1-x)/y
设 t = y/(1+x)
tx-y=-t; x+ty=1;
另 t = u/v [t为有理数]
a/c = (v^2 - u^2)/(u^2+v^2)
b/c = (2uv)/(u^2+v^2)
u,v互素 且有一个奇数 v>u, a = v^2 - u^2; b = 2uv c = u^2 + v^2
Pell
x^2-ay^2 = 1
xn = ((x1+d^0.5*y1)^n+(x1-d^0.5*y1)^n)/2
yn = ((x1+d^0.5*y1)^n-(x1-d^0.5*y1)^n)/2d^0.5
xn = x1xn-1 + dy1yn-1
yn = y1xn-1 + x1yn-1
文章来源: http://thunderfyc.wordpress.com.cn
=================================================================================
猫的帽子里总有n个小猫，小猫又有小小猫，小猫的高度是猫的1/(n+1)，
最小的猫高为1，已知最大的猫高度和最小的猫数，求除了最小猫的数量和所有猫的高度和
H0 = (N+1)^dep;
workNum = N^dep;
ln(H0) = dep*ln(N+1); ln(workNum) = dep*lnN;
ln(H0)/ln(workNum) = ln(N+1)/ln(N); [此方程y -> 1 精度会有问题]
ln(H0)/ln(H0/workNum) = ln(N+1)/ln((N+1)/N) = ln(N+1) / ln(1 + 1/N)
y = ln(N+1) / ln(1+ 1/N) [增函数]
用Newton-Raphson 牛顿迭代法解（随便一个初始值，从函数上此点作切线，和x轴交点为新的值）
x = x0 - f(x0)/f’(x0) 迭代几次就可以了
notWorkNum = 1 + N + N^2 + … + N^(dep-1) = (N^dep - 1)/(N-1) = (workNum - 1)/(N-1);
HSum = 1 + (N+1)+(N+1)^2 + … + (N+1)^dep = ((N+1)^(dep+1) - 1)/N = (H0*(N+1) - 1)/N;
求数a b 满足1+2+..+a-1 = a+1+…+b
做方程a*(a-1) = (a+t+1+a+1)*(t+1) x^2-2y^2 = 1
x = 2t+2a+3 y = 2a
用Pell方程求解
xn = x0*xn-1 + 2*y0*yn-1
yn = x0*yn-1 + y0*xn-1
=============================================================================
Bignum Plus(a,b:Bignum)
{
for i <- 0 to maxn
{
c[i] = a[i]+b[i];
c[i+1] += c[i] div 1000;
c[i] = c[i] mod 1000;
}
return c;
}
Bignum Minus(a,b:Bignum)
{
if (less(a,b))
return Minus(b, a);
for i <- 0 to maxn
{
if (b[i] < a[i])
{
b[i+1]-1;
b[i]+1000;
}
c[i] = b[i]-a[i];
c[i+1] += c[i] div 1000;
c[i] = c[i] mod 1000;
}
return c;
}
Bignum Multi(a,b:Bignum)
{
for i <- 0 to maxn
{
c = 0;
for j <- 0 to maxn
{
c[i+j] = a[i]*b[j];
c[i+j+1] += c[i+j] div 1000;
c[i+j] = c[i+j] mod 1000;
}
d = Plus(d, c);
}
return d;
}
文章来源: http://thunderfyc.wordpress.com.cn
