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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#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; } |