#28. canal — the nineteenth test of Yucai OJ

Problem description

In the city of N, the location of n city is just the vertex, just forming a positive n shape. In order to promote the development of trade, it is necessary to open several canals (the number of canals can be 0) between certain cities. The canals must be opened in a straight line, starting and ending in two different cities.It means that the two canals cannot intersect (the two canals share a city as the starting and ending point), otherwise, there will be war between the cities because of the cost of water used in the canal. The number of schemes for opening the canal.

Input format

One line and one integer n.

Output format

Because the result may be very large, you only need to output the value of this answer mod 12345.

sample input

sample output

Data size and agreement

For the 30% data:

For the 50% data:

For the 100% data:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int inf=1000000000;
 4 const int mod=12345;
 5 const int D=1000;
 6 long long f[D+1];
 7 void init(){
 8     f[0]=1;
 9     f[1]=1;
10     f[2]=2;
11     for(int i=3;i<=D;++i){
12         f[i]=0;
13         for(int j=0;j<=i-2;++j){
14             f[i]+=f[j]*f[i-j-2];
15         }
16         f[i]+=f[i-1];
17         if(f[i]>inf){
18             f[i]%=mod;
19         }
20     }
21     return;
22 }
23 int main(){
24     int n;
25     init();
26     cin>>n;
27     cout<<f[n]%mod<<endl;
28     return 0;
29 }

Standard range