Handshaking<DP>

链接:http://soj.me/show_problem.php?pid=1007&cid=969

N (N is even) persons stand around a round table. They make handshakes. Every person shakes the hand with one and exactly one of other persons. All handshakes are made at the same time. Your task is to calculate how many ways of handshaking can be made if arm crossing is not allowed.

Input

The input begins with a line containing an integer T (T<=1000), which indicates the number of test cases. The following T lines each contain an even number N (2<=N<=2000), indicating the number of persons.

Output

For each case, output the number of ways. The answer may be very large, so just output the remainder of the answer after divided by 1000000007.

Sample Input

Copy sample input to clipboard

Sample Output

题意:有N个人要互相握手, 问两两不相交叉有多少种

思路: dp题 dp[i] 表示i个人的种数;

枚举1和谁握手, 则可分为 i-2, 和 N-i 两部分

View Code

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <string>
 6 #include <stdlib.h>
 7 using namespace std;
 8 const int Mod=1e9+7;
 9 long long dp[2005];
10 void Init( )
11 {
12     memset( dp, 0, sizeof dp ); 
13     dp[0]=1; dp[2]=1;
14     for( int i=4; i<=2001; i+=2 )
15         for( int j=2; j<=i; ++j ){
16             dp[i]+=(dp[j-2]*dp[i-j])%Mod;
17             dp[i]%=Mod;
18         }
19 }
20 int main( )
21 {
22     Init( );
23     int T, N;
24     scanf( "%d", &T );
25     while( T -- ){
26         scanf( "%d", &N );
27         printf( "%lld\n", dp[N] );
28     } 
29     return 0;
30 }