UOJ #574. 桂林的文件

【题目描述】：

桂林有N个不同的文件，现在他要创建N-1个文件夹（相同）来保存这些文件，每个文件夹内有且只有两个项目，每个项目可以是一个文件或者一个文件夹，问他有多少种不同的存储方式。

【输入描述】：

第一行一个正整数T，表示数据组数。

接下来T行每行一个正整数N。

【输出描述】：

共T行，在模19260817的意义下桂林的存储方式总数。

【样例输入】：

2
3
5

【样例输出】：

3
105

【时间限制、数据范围及描述】：

时间：1s 空间：256M

30%的数据：2≤N≤20；

70%的数据：2≤N≤1000；

100%的数据：T≤100, 2≤N≤10^6

思路

根据排列组合易得：f[1]=1,f[2]=1,f[3]=C(3,1)=3,f[4]=C(3,1)*f[1]*f[3]+C(2,2)*f[2]*f[2]/2(有重复情况，自己手动模拟一下就能发现)=15,f[5]=105...

仔细观察：1=1,3=1*3,15=1*3*5,105=1*3*5*7...发现了吗？

这是一个奇数数列的积（一开始被老师带歪了，Ta告诉我这题不能偷懒，不要找规律，这不是数论题，去建树吧。。。）

代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2000010;
const int Mod=19260817;

int t,n;
long long x[N];

int main () {
	x[0]=x[1]=1;
	for(int i=2; i<=N; i++)
		x[i]=x[i-2]*i%Mod;
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		printf("%d\n",x[2*n-3]);
	}
	return 0;
}