d230 - IOI研習營模考2-1三元樹

Sylveon

原文：http://zerojudge.tw/ShowProblem?problemid=d230
AC   ：http://zerojudge.tw/Submissions?problemid=d230&account=lfs92002
ACCODE：http://ideone.com/L1pMBW
廣義卡特蘭數，代公式Tk(n) = 1/((k-1)*n)*C(k*n,n)就OK，只是MOD的數字不是質數，無法使用逆元(乘法反元素)來處理除法，在此使用了約分法來進行除法的部分。應該可以DP，只是我懶得推公式XD

/**********************************************************************************/
/*  Problem: d230 "IOI研習營模考2-1三元樹" from IOI                       */
/*  Language: CPP (644 Bytes)                                                     */
/*  Result: AC(0.4s, 288KB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2014-03-14 09:16:05                                       */
/**********************************************************************************/


#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 10000000
int base[15001];
inline int gcd(int a,int b)
{
        while((a%=b)&&(b%=a));
        return a+b;
}
int main()
{
        int n;
        int p,j;
        while(~scanf("%d",&n))
        {
                for(int i=2*n+1;i<=3*n;++i)
                        base[i]=i;
                for(int i=1;i<=n;++i)
                {
                        p=i,j=2*n+1;
                        while(p!=1)
                        {
                                int d=gcd(p,base[j]);
                                p/=d;
                                base[j++]/=d;
                        }
                }
                p=2*n+1;
                j=2*n+1;
                while(p!=1)
                {
                        int d=gcd(p,base[j]);
                        p/=d;
                        base[j++]/=d;
                }
                long long ans=1;
                for(int i=2*n+1;i<=3*n;++i)
                        ans=ans*base[i]%MOD;
                printf("%lld\n",ans);
        }
        return 0;
}