TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原文: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;
}
|
|