2014
01-26

# Counting Problem

Yes. Counting problem comes again.
Given a chess board of N*N (N<=500), how many ways are there to put N queens on it so that no queen can attack another?
Luckily this is not the problem you should solve in this contest. Instead, we have a much easier one here.
Given a chess board of N*N (N<=500), how many ways are there to put 2*N queens on it so that there are exactly two queens in each row and each column?
To make it even easier, we will consider one way to be the same with another if it can be transformed to the other one by swapping rows and swapping columns.

The first line of the input is an integer T indicating the number of cases.
Line 2..T+1 will contain an positive integer N (N <=500) each.

The first line of the input is an integer T indicating the number of cases.
Line 2..T+1 will contain an positive integer N (N <=500) each.

3
2
5
4

1
2
2

/***************************************
* File Name:2431.cpp
* Created Time:2013年12月14日 10:56:21
***************************************/
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 501;
const int mod = 1000007;
int f[maxn];

void init(){
f[0] = 1;
for (int i=2; i<maxn; i++){
for (int j=i; j<maxn; j++){
f[j] += f[j-i];
if (f[j] >= mod){
f[j] -= mod;
}
}
}
}
int main(){
int T;
int n;
init();
scanf("%d",&T);
while (T--){
scanf("%d",&n);
printf("%d\n",f[n]);
}
return 0;
}

1. 两种生活我都体验过，五星级酒店睡过，同样也睡过20块钱的地下室。经历得多了反而不太在意外部环境了，因为自己有适应能力了。人不是不能改变环境，而是没必要去改变，只要改变了自己就行了。一劳永逸~~~~~~~~~总之我是看淡了，没有攀比心也没什么虚荣心了，内心

2. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法