4222: Edge Case

# Edge Case ### 内存 256MB ### 时间 1S ## 题目描述 $n（3\le n\le 10000）$个结点组成一个圈，求匹配（即没有公共点的边集）的个数。比如$n=4$时有7个（如上图),$n=100$时有792070839848372253127个。 环图$C_n(n≥3)$是一个简单无向图,其顶点集为${1,...,n}$,包含$n$条边。图$a$描绘了图$C_3、C_4、C_5$和$C_6$。   图$a:C_4$的匹配。属于相应匹配的边用绿色表示,而未包含在匹配中的边用虚线表示。$M_1 = ∅,M_2 = {{2, 1}},M_3 = {{3, 2}},M_4 = {{4, 3}},M_5 = {{1, 4}},M_6 = {{2, 1},{4, 3}}$,以及$M_7 = {{3, 2},{1, 4}}$。 ## 输入格式 每行输入包含一个正整数：$n$，其中$3≤n≤10000$。 ## 输出格式 对于每行输出，一行包含$C_n$中的匹配数。 ## 输入输出样例 ### 输入样例1 ``` 3 4 100 ``` ### 输出样例1 ``` 4 7 792070839848372253127 ``` ## 数据范围与提示 $3≤n≤10000$ ## 题目来源 ACM/ICPC NWERC 2012