SRM 618 DIV1 500

非常棒的组合问题，看了好一会，无想法....

有很多做法，我发现不考虑顺序的最好理解，也最好写。

结果一定是两种形式

A....A   dp[n-1]

A...A...A sgma(dp[j]*dp[n-j-1])( 1<=j<=n-2)

最后乘上n！

什么时候才能自己在比赛中做出一个500分来啊！！！

class LongWordsDiv1
{
public :
    int count(int n)
    {
        int i,j;
        fact[0] = 1;
        for(i = 1; i <= n; i ++)
        {
            fact[i] = (i*fact[i-1])%MOD;
        }
        dp[1] = 1;
        dp[2] = 1;
        for(i = 3; i <= n; i ++)
        {
            dp[i] = dp[i-1];
            for(j = 1; j < i-1; j ++)
            {
                dp[i] = (dp[i] + (dp[j]*dp[i-j-1])%MOD)%MOD;
            }
        }
        return (dp[n]*fact[n])%MOD;
    }
};