답안 #19700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19700 2016-02-25T04:42:45 Z ainta 괄호 (kriii4_R) C++
100 / 100
974 ms 48348 KB
#include<stdio.h>
#include<algorithm>
using namespace std;
long long Mod = 1000000007, K, F[2010000], Inv[1010000], InvF[1010000], D[1010000], Po[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;
}
int main(){
    int i;
    scanf("%d%lld",&n,&K);
    Po[0]=F[0]=InvF[0]=1;
    for(i=1;i<=2000000;i++)F[i] = F[i-1]*i%Mod;
    for(i=1;i<=1000000;i++){
        Po[i] = Po[i-1]*K%Mod;
        Inv[i] = GetInv(i);
        InvF[i] = InvF[i-1]*Inv[i]%Mod;
    }
    D[1] = K;
    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*Po[i/2]%Mod;
        else tp = 0;
        D[i+1] = ((D[i]-tp+Mod)%Mod*(K+1)%Mod + tp*K)%Mod;
    }
    printf("%lld\n",D[n]);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 897 ms 48348 KB Output is correct
2 Correct 873 ms 48348 KB Output is correct
3 Correct 938 ms 48348 KB Output is correct
4 Correct 953 ms 48348 KB Output is correct
5 Correct 952 ms 48348 KB Output is correct
6 Correct 903 ms 48348 KB Output is correct
7 Correct 903 ms 48348 KB Output is correct
8 Correct 903 ms 48348 KB Output is correct
9 Correct 874 ms 48348 KB Output is correct
10 Correct 868 ms 48348 KB Output is correct
11 Correct 868 ms 48348 KB Output is correct
12 Correct 944 ms 48348 KB Output is correct
13 Correct 935 ms 48348 KB Output is correct
14 Correct 898 ms 48348 KB Output is correct
15 Correct 896 ms 48348 KB Output is correct
16 Correct 891 ms 48348 KB Output is correct
17 Correct 955 ms 48348 KB Output is correct
18 Correct 958 ms 48348 KB Output is correct
19 Correct 964 ms 48348 KB Output is correct
20 Correct 973 ms 48348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 899 ms 48348 KB Output is correct
2 Correct 869 ms 48348 KB Output is correct
3 Correct 885 ms 48348 KB Output is correct
4 Correct 960 ms 48348 KB Output is correct
5 Correct 926 ms 48348 KB Output is correct
6 Correct 931 ms 48348 KB Output is correct
7 Correct 921 ms 48348 KB Output is correct
8 Correct 900 ms 48348 KB Output is correct
9 Correct 916 ms 48348 KB Output is correct
10 Correct 877 ms 48348 KB Output is correct
11 Correct 928 ms 48348 KB Output is correct
12 Correct 951 ms 48348 KB Output is correct
13 Correct 947 ms 48348 KB Output is correct
14 Correct 901 ms 48348 KB Output is correct
15 Correct 911 ms 48348 KB Output is correct
16 Correct 902 ms 48348 KB Output is correct
17 Correct 876 ms 48348 KB Output is correct
18 Correct 974 ms 48348 KB Output is correct
19 Correct 973 ms 48348 KB Output is correct
20 Correct 962 ms 48348 KB Output is correct