Pills
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.
On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.
In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle?
1
4
2
3
30
0
1
14
2
5
3814986502092304
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=2e5+,M=4e6+,inf=1e9+,mod=1e9+;
const ll INF=1e18+;
ll dp[][];
void init()
{
for(int i=;i<=;i++)
dp[][i]=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
if(j==)
dp[i][j]=dp[i-][j+];
else
dp[i][j]=dp[i-][j+]+dp[i][j-];
}
}
int main()
{
init();
int n;
while(~scanf("%d",&n))
{
if(n==)break;
printf("%lld\n",dp[n][]);
}
return ;
}