Submission #19673

#	Time	Username	Problem	Language	Result	Execution time	Memory
19673		ainta	괄호 (kriii4_R)	C++98	0 / 100	884 ms	40456 KiB

R

#include<stdio.h>
#include<algorithm>
using namespace std;
long long Mod = 1000000007, K, F[2010000], Inv[1010000], InvF[1010000], D[1010000];
int n;
long long GetInv(long long a){
    int b = Mod-2;
    long long r = 1;
    while(b){
        if(b&1)r=r*a%Mod;
        a=a*a%Mod;b>>=1;
    }
    return r;
}
long long GetPow(long long a, int b){
    long long r = 1;
    while(b){
        if(b&1)r=r*a%Mod;
        a=a*a%Mod;b>>=1;
    }
    return r;
}
int main(){
    int i;
    scanf("%d%lld",&n,&K);
    F[0]=InvF[0]=1;
    for(i=1;i<=2000000;i++)F[i] = F[i-1]*i%Mod;
    for(i=1;i<=1000000;i++){
        Inv[i] = GetInv(i);
        InvF[i] = InvF[i-1]*Inv[i]%Mod;
    }
    D[1] = 1;
    long long tp;
    for(i=1;i<n;i++){
        tp = F[2*i]*InvF[i]%Mod*InvF[i]%Mod*Inv[i+1]%Mod;
        D[i+1] = ((D[i]-tp+Mod)%Mod*2 + tp)%Mod;
    }
    printf("%lld\n",D[n]*GetPow(K,n)%Mod);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92