Submission #19700

#	Time	Username	Problem	Language	Result	Execution time	Memory
19700		ainta	괄호 (kriii4_R)	C++98	100 / 100	974 ms	48348 KiB

R

#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]);
}

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