TIOJ 1607 Problem A 山稜線 (CATALN)

[DP+模逆]
把卡特蘭數炸開就可以了= =

複雜度：

卡 unsigned long long int 卡超久= =

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define LL unsigned long long int
LL MOD = 1000000007;
LL _POW(LL a,LL n)
{
    a%=MOD;
    //printf("_POW(%I64d,%I64d)\n",a,n);
    if(a<=1) return a;
    if(n==0) return 1;
    if(n==1) return a;
    LL k = _POW(a,n/2);
    if(n%2==0) return (k*k)%MOD;
    else    return (k*((k*a)%MOD))%MOD;
}
LL dp[500001];
LL Sn[500001];
int main()
{
    //printf("D=%I64d\n",_POW(10,MOD-1));
    int T;scanf("%d",&T);
    LL S2n=1;
    Sn[0]=1;
    for(LL prc=1;prc<=500000;prc++)
    {
        Sn[prc]=(Sn[prc-1]*prc)%MOD;
        S2n=(((((prc*(2*prc-1))%MOD)*2)%MOD)*S2n)%MOD;
        //LL D=(((Sn*(prc+1))%MOD)*(Sn))%MOD;
        //printf("D=%I64d\n",_POW(100,MOD-1));
        //D=_POW(D,MOD-2);
        dp[prc]=S2n;
    }
    while(T--)
    {
        int n;scanf("%d",&n);n/=2;
        LL D=(((Sn[n]*(n+1))%MOD)*(Sn[n]))%MOD;
        D=_POW(D,MOD-2);
        printf("%I64u\n",(dp[n]*D)%MOD);
    }
    return 0;
}