991

Theory:

For larger n, imagine choosing an arbitrary pair of people to shake hands. You’ve now divided the circle into two smaller circles (one of which may have 0 people in it). The number of ways you can arrange the rest of the people is the product of the answers for the two smaller circles.

#include <iostream>

using namespace std;
//unsigned long long
int arr[12];

int main()
{

arr[0]=1;
arr[1]=1;
arr[2]=2;
for(int i=3;i<12;i++)
arr[i]=0;

int k,j,n,c=0;

for(int i=3;i<12;i++)
{
k=i-1;
j=0;
arr[i]+=arr[k]*arr[j];
while(k)
{
arr[i]+=arr[k]*arr[j];
j++;k--;
}
}

while(cin>>n)
{
if(c)
cout<<"\n";
c=1;
cout<<arr[n]<<"\n";
}

return 0;
}