一些刷题过程中的结论

来源UVA 10313 整数i拆分成不超过j个整数的拆分方案数，是和整数i拆成若干个值不超过j的整数的拆分方案数是相同的

原理 Ferrers图像详：http://blog.csdn.net/shiqi_614/article/details/7001949

关于C++引用带的的不易发现的错误。来自于一个4维DP。UVA 10913 例如int&res=dp[i][j][p][q].如果在这个记忆化搜索子过程中需要更新i,j,p,q;比如在当前递归中p++，那么此时的res是dp[i][j][p-1][q];而不是更新的dp[i][j][p(执行p++之后[q];

http://vjudge.net/contest/viewSource.action?id=2590324

double类型，POJ出现%lf WA %f AC.为啥就暂且放下，，

矩形主副对角线存在坐标和相等，坐标差相等的规律。两点横纵坐标和互为奇偶则两点不在同一主副对角线上。source:codeforces 264 C

手算开平方：例

26244进行开平方：

1)对26244进行划分，从最后两位两位的向前划分，结果为2 62 44

2)从最高分段开始计算：只有1 平方小于2，第一次运算的结果为，被除数是2，除数是1，商是1，余数是1

3)用余数1和接下来的两位组成新数162，用公式商（1*20+X）*X<=162，试探后x = 6，则本次运算的结果是

被除数是162，除数是（1*20+X）=26，商是6，余数是162 - （20+6）*6 = 6；

4)用余数6和接下来的两位组成新书644，用公式（16*20+X）*X<=644，试探得x = 2，则本次运算的结果是

被除数是644，除数是（16*20+X）=322，商是2，余数是0；

则最后的结果是162；

斐波那契素数:与所有比其小的斐波那契数互质的素数；定理：从第5项开始，某项位斐波那契素数当且仅当他的项数位素数即3,4,5,7.....项位斐波那契素数。黑书221

设字符一空K类，个数分别是n1,n2,n3...nk则这个多重级的全排列个数是（n1+n2+n3....nk)!/n1!*n2!*....*nk!

UVALIVE 2955 关于梅森素数

我们把满足 E = 2 ^ i - 1 的素数E称作梅森素数。

关于梅森素数，有一个重要的定理：“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”，但是不能重复，比如说3是梅森素数，9就不满足约数和为2的幂。详见UVALIVE 2955

对于最大流无向图双向建边是4条边。临接表建图注意反向容量为0。如果有向图同样也是反向边为0.邻接矩阵可以直接memset(cap,0); //总结的暂时可能需要纠正。

关于点联通度边联通度

http://hi.baidu.com/lerroy312/item/5a5f36f2f5bba61bcf9f322e

竞赛图:图中的任意两点间有且仅有一条有向弧连接

求竞赛图中的哈密顿路的算法：

首先,由数学归纳法可证竞赛图在n>=2时必存在哈密顿路；

(1)n=2时显然；

(2)假设n=k时,结论成立,哈密顿路为V1,V2,...,Vi,...,Vk；

现添加第k+1个结点，若存在弧<Vi,Vk+1>和弧<Vk+1,Vi+1>，则可得哈密顿回路V1,V2,...,Vi,Vk+1,Vi+1,...,Vk；

若不存在上述的vi,考虑到Vk+1与v1~vk的连通状况,则只有下面种原哈密顿路的情况：

1.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vi,Vk+1>，那么可得哈密顿回路V1,V2,...,Vi,...,Vk,Vk+1；

2.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vk+1,Vi>，那么可得哈密顿回路Vk+1,V1,V2,...,Vi,...,Vk；

3.存在一个中间结点m，使得所有的Vi(1<=i<=m)与Vk+1的弧方向为<Vk+1,Vi>,所有的Vj(m<j<=k)与Vk+1的弧的方向为<Vj,Vk+1>，这时依然可以构造哈密顿路 V1,V2,...,Vi,...,Vk,Vk+1；

引用：http://blog.csdn.net/dgq8211/article/details/7602807

有一堆个数为n的石子，游戏双方轮流取石子，满足：

1)先手不能在第一次把所有的石子取完；

2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。

约定取走最后一个石子的人为赢家，求必败态。

这个和之前的Wythoff’s Game 和取石子游戏有一个很大的不同点，就是游戏规则的动态化。之前的规则中，每次可以取的石子的策略集合是基本固定的，但是这次有规则2：一方每次可以取的石子数依赖于对手刚才取的石子数。

这个游戏叫做Fibonacci Nim，肯定和Fibonacci数列：f[n]：1,2,3,5,8,13,21,34,55,89,… 有密切的关系。如果试验一番之后，可以猜测：先手胜当且仅当n不是Fibonacci数。换句话说，必败态构成Fibonacci数列。

anti-num 普通去石子游戏取光着输，结论 http://blog.csdn.net/acm_cxlove/article/details/7854530 定义：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。
定义：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充裕堆的堆数等于0，则称为部分利他态，用T0表示。

必败态： T2,S0
必胜态： S2,S1,T0.

先手必胜（1）当且仅当所有石子数为1，且游戏SG值为0；有些堆的石子数大于1，且SG不为0；

题目：多棵树，删边游戏，最后一次操作的人输

其中树的删边游戏：叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1 后的异或和。

ANTI-SG:先手必胜当且仅当：（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。

K倍动态减法http://blog.csdn.net/acm_cxlove/article/details/7836544

C(n,2*(i+1))*CAN(i+1)=(n-2*i)*(n-2*i-1)/(i+1)/(i+2) * (C(n,2*i)*CAN(i))

A^x % m = A^(x%phi(m)+phi(m)) % m (x >= phi(m))

若一个数可以写成若干个不同的梅森素数的乘积，那么这个数的所以因子和可以写成

也可以写作：若p为质数，则p可整除(p-1)!+1

LUCAS定理

A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。
则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) modp同余

即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)

//有这么个公式cosa=cosb*cosc+sinb*sinc*cosA
//其中小写a,b,c表示球面三角形边长所对应的圆心角 大写A表示三角形内角，求球面三角形内角可用
struct node
{
    double x,y;
};
//计算圆心角lat表示纬度，lng表示经度，-90 <= w <= 90;
//计算两点所在大圆劣弧对应圆心角，0 <= angle <= pi;
double angle(double lng1,double lat1,double lng2,double lat2)
{
    double dlng = fabs(lng1 - lng2) * PI / 180;
    while(dlng + eps > PI + PI)
        dlng -= PI + PI;
    if (dlng > PI) dlng = 2 * PI - dlng;
    lat1 *= PI / 180; lat2 *= PI / 180;
    return acos(cos(lat1) * cos(lat2) * cos(dlng) + sin(lat1) * sin(lat2));
}