oj.uz

Submission #19679

# Submission time Handle Problem Language Result Execution time Memory
19679 2016-02-25T04:28:46 Z ainta 괄호 (kriii4_R) C++
8 / 100
 925 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++){
        if(i%2==0)tp = F[i]*InvF[i/2]%Mod*InvF[i/2]%Mod*Inv[i/2+1]%Mod;
        else tp = 0;
        D[i+1] = ((D[i]-tp+Mod)%Mod*2 + tp)%Mod;
    }
    printf("%lld\n",D[n]*GetPow(K,n)%Mod);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 40456 KB Output is correct
2 Correct 857 ms 40456 KB Output is correct
3 Correct 901 ms 40456 KB Output is correct
4 Correct 910 ms 40456 KB Output is correct
5 Correct 907 ms 40456 KB Output is correct
6 Correct 878 ms 40456 KB Output is correct
7 Correct 882 ms 40456 KB Output is correct
8 Correct 871 ms 40456 KB Output is correct
9 Correct 863 ms 40456 KB Output is correct
10 Correct 848 ms 40456 KB Output is correct
11 Correct 853 ms 40456 KB Output is correct
12 Correct 910 ms 40456 KB Output is correct
13 Correct 903 ms 40456 KB Output is correct
14 Correct 868 ms 40456 KB Output is correct
15 Correct 878 ms 40456 KB Output is correct
16 Correct 870 ms 40456 KB Output is correct
17 Correct 909 ms 40456 KB Output is correct
18 Correct 916 ms 40456 KB Output is correct
19 Correct 919 ms 40456 KB Output is correct
20 Correct 925 ms 40456 KB Output is correct

Subtask #2
0.0 / 92.0

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