oj.uz

Submission #19673

# Submission time Handle Problem Language Result Execution time Memory
19673 2016-02-25T04:26:17 Z ainta 괄호 (kriii4_R) C++
0 / 100
 884 ms 40456 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 884 ms 40456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 92.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -