#
//一、当n mod 6 != 2 且 n mod 6 != 3时，有一个解为：
//
//2,4,6,8,...,n,1,3,5,7,...,n-1 (n为偶数)
//
//2,4,6,8,...,n-1,1,3,5,7,...,n (n为奇数)
//
//(上面序列第i个数为ai，表示在第i行ai列放一个皇后；... 省略的序列中，相邻两数以2递增。下同)
//
//二、当n mod 6 == 2 或 n mod 6 == 3时，
//
//(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)
//
//k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1 (k为偶数,n为偶数)
//
//k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n (k为偶数,n为奇数)
//
//k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1 (k为奇数,n为偶数)
//
//k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n (k为奇数,n为奇数)
摘要: 很高兴在完全没有参考任何代码的前提下通过此题，呵呵，就是代码比较猥琐，跑得也比较慢，2700MS,超过时限的一半了。此题应该还有继续提升的空间，我想了想，insert函数和query其实是可以放在一起的。另外网上的方法用了反素数 这样可以减少插入的次数，应该也能剪去一下时间。下次试试。^_^顺便用此题做为POJ 500题纪念
#include<iostream>using ...
阅读全文
关于扩展的卡特兰数：
1.(n-m+1)/(n+1)*c(n+m,n)
2.c[n+m][n]-c[n+m][m-1]
Catalan，Eugene，Charles，卡特兰（1814～1894）比利时数学家，生于布鲁日（Brugge），早年在巴黎综合工科学校就读。1856年任列日（Liege）大学数学教授，并被选为比利时布鲁塞尔科学院院士。
卡特兰一生共发表200多种数学各领域的论著。在微分几何中，他证明了下述所谓的卡特兰定理：当一个直纹曲线是平面和一般的螺旋面时，他只能是实的极小曲面。他还和雅可比（Jacobi，C·G·J）同时解决了多重积分的变量替换问题，建立了有关的公式。
1842年，他提出了一种猜想：方程xz－yt＝1没有大于1的正整数解，除非平凡情形32－23＝1。这一问题至今尚未解决。
（mathoe注：即除了8、9这两个连续正整数都是正整数的方幂外，没有其他。1962年我国数学家柯召以极其精湛的方法证明了不存在三个连续正整数，它们都是正整数的方幂，以及方程x2－yn＝1，n＞1，xy≠0无正整数解。并且还证明了如果卡特兰猜想不成立，其最小的反例也得大于1016。）
此外，卡特兰还在函数论、伯努利数和其他领域也做出了一定的贡献。
卡特兰通过解决凸n边形的剖分得到了数列Cn。
凸n＋2边形用其n－1条对角线把此凸n＋2边形分割为互不重叠的三角形，这种分法的总数为Cn。
为纪念卡特兰，人们使用“卡特兰数”来命名这一数列。
据说有几十种看上去毫不相干的组合计数问题的最终表达式都是卡特兰数的形式。
卡特兰数在数学竞赛、信息学竞赛、组合数学、计算机编程等都会有其不同侧面的介绍。
前几个卡特兰数：规定C0＝1，而
C1＝1，C2＝2，C3＝5，C4＝14，C5＝42，
C6＝132，C7＝429，C8＝1430，C9＝4862，C10＝16796，
C11＝58786，C12＝208012，C13＝742900，C14＝2674440，C15＝9694845。
递推公式
圆周上有标号为1，2，3，4，……，2n的共计2n个点，这2n个点配对可连成n条弦，且这些弦两两不相交的方式数为卡特兰数Cn。
2003年浙江省小学数学夏令营竞赛考了这个题：圆周上10个点可以连成既不相交，也没有公共端点的5条线段，不同的连法共有_____种。
答：方法的种数是卡特兰数C5＝42，此题被收录进单墫主编的知识出版社出版的《华数奥赛强化训练》小学六年级册的“计数问题”专题。
共六种类型，第1类有5种连法，第2类有2种连法，第3类有10种连法，第4类有10种连法，第5类有10种连法，第6类有5种连法。共有42种连法。
1994年《小学数学》有奖征答竞赛：游乐园门票1元一张，每人限购一张。现在有10个小朋友排队购票，其中5个小朋友每人只有1元的钞票一张，另5个小朋友每人只有2元的钞票一张，售票员没有准备零钱。问：有多少种排队方法，使售票员总能找的开零钱？
（此题也被许多奥数资料收录为例题或习题，《华罗庚学校数学课本》小学六年级册的思维训练也收有此题）
答：现把拿1元的5个小朋友看成是相同的，把拿2元的5个小朋友也看成是相同的，使用我们常用的“逐点累加法”：
图中每条小横段表示拿1元的小朋友，每条小竖段表示拿2元的小朋友，要求从A走到B的过程中网格中任何点均有横段数不小于竖段数：拿1元的要先，且人数不能少于拿2元的，即不能越过对角线AB：每个点所标的数即为从A走到此点的方法数。求从A到B的走法的方法数。逐点累加可求出为42，即卡特兰数C5＝42。
又由于每个小朋友是不相同的，所以共有42×5！×5！＝42×120×120＝604800种情况。
若把此题的10个人，拿1元的有5人，拿2元的有5人改为共有2n个人，拿1元的n人，拿2元的n人，则符合要求的排队方法数为：
再一个卡特兰数的例子：
甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的种数。
即甲在得到1分到19分的过程中始终领先乙，其种数是卡特兰数
再一个卡特兰数的例子
饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？
答：得数是第n个卡特兰数Cn。
再一个卡特兰数的例子
一个汽车队在狭窄的路面上行驶，不得超车，但可以进入一个死胡同去加油，然后再插队行驶，共有n辆汽车，问共有多少种不同的方式使得车队开出城去？
答：得数是第n个卡特兰数Cn。
卡特兰数
求证：卡特兰数Cn是整数。
证明：
①取整函数不等式：对任意实数x，y有[x＋y]≥[x]＋[y]。这里[x]表示不大于实数x的最大整数。
解：由定义x≥[x]……（1）
y≥[y]……（2）以上两式相加，得：x＋y≥[x]＋[y]，
把上式再取整，得：[x＋y]≥[[x]＋[y]]＝[x]＋[y]，即[x＋y]≥[x]＋[y]。
②1000！的末尾0的个数249个。（现在有的小学奥数书上出现了100！末尾有几个零的题目：24个）
解：1000÷5＝200，
200÷5＝40，
40÷5＝8，
8÷5＝1……3
以上各商相加，即得1000！末尾0的个数＝200＋40＋8＋1＝249个。
③n！的质因数分解式中质因子p的幂次数：
…………（1）
k！的质因数分解式中质因子p的幂次数
…………（2）
(n－k)!的质因数分解式中质因子p的幂次数
…………（3）
这里写成西格马求和式时使用了无穷的形式，但是从某一确定项之后的每项都是0，为了统一，都写成了“∞”形式。
④组合数是整数
解：
⑤卡特兰数是整数
⑥卡特兰数是整数的另外一个证明
④组合数是整数
⑤卡特兰数是整数
⑥卡特兰数是整数的另一个证明
凸六边形剖分成三角形的14种方法，是卡特兰数C4
从左下角（0，0）走到右上角（4，4），只允许向上、向右走，但不允许穿过对角线的方法数是14种，是卡特兰数C4
1936第40届匈牙利奥林匹克数学竞赛 第1题考了Catalan恒等式的证明。
1979第21届国际数学奥林匹克 第1题考了一个卡特兰恒等式的应用的题目
此题由1989年第1届匈牙利-以色列数学竞赛题改编。
转自：
http://www.mathoe.com/dispbbs.asp?boardid=89&replyid=46004&id=34522&page=1&skin=0&Star=2
问题
《编程之美》中提到了“买票找零”问题，查阅了下资料，此问题和卡特兰数 Cn有关，其定义如下：
卡特兰数真是一个神奇的数字，很多组合问题的数量都和它有关系，例如：
一.Cn= 长度为 2n的 Dyck words的数量。 Dyck words是由 n个 X和 n个 Y组成的字符串，并且从左往右数， Y的数量不超过 X，例如长度为 6的 Dyck words为：
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
二.Cn= n对括号正确匹配组成的字符串数，例如 3对括号能够组成：
((())) ()(()) ()()() (())() (()())
三.Cn= n+1个数相乘，所有的括号方案数。例如， 4个数相乘的括号方案为：
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
\四.Cn= 拥有 n+1 个叶子节点的二叉树的数量。例如 4个叶子节点的所有二叉树形态：
五.Cn=n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数，例如， 4×4方格地图中的路径有：
六.Cn= n+2条边的多边形，能被分割成三角形的方案数，例如 6边型的分割方案有：
七.Cn= 圆桌周围有 2n个人，他们两两握手，但没有交叉的方案数。
在《Enumerative Combinatorics》一书中，竟然提到了多达 66种组合问题和卡特兰数有关。
摘要: A 就是分数化简注意一下就好，gcdB.暴力，1个trick , 当时间相同时要求的是 到学校距离最小的那个站
#include<iostream>#include<cmath>using namespace std;struct point{ double x; ...
阅读全文
摘要: 之前想进行hash,发现思路非常麻烦。索性来个一一对应，找到第一个M后，扫描所有52个字母，一个字母正反各算一次，找准基准点后，用一张7*16的图进行覆盖，整张图要完全一一对应。 为了避免附近字母的干扰，先做一遍深搜，只对深搜搜过的点进行对应，其他的不管。
#include<iostream>using namespace std;char s[26][...
阅读全文
题意严重不明，开始还以为是顶点按顺序形成环，WA了N次之后改了算法才过的。。。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m;
int v[100][100];
int d[100];
int f[1000];
int r[1000];
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int flag=0;
memset(d,0,sizeof(d));
int i,j;
for(i=0;i<n;i++)
{
f[i]=i;
r[i]=1;
}
for(i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
d[a]++;
d[b]++;
}
int tt=find(1);
if(r[tt]!=n)
{
printf("NO\n");
continue;
}
if(n!=m||n<3)
{
printf("NO\n");
continue;
}
for(i=1;i<=n;i++)
{
if(d[i]!=2)
{
flag=1;
break;
}
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}