제출 #20091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20091		jihoon	괄호 (kriii4_R)	C++98	100 / 100	702 ms	24520 KiB

R

#include<cstdio>
#define je 1000000007
long long fact[2000001];
long long seq[1000001];

long long gop(long long x,long long y){
	x%=je;y%=je;
	x*=y;x%=je;
	return x;
}

long long hap(long long x,long long y){
	x%=je;y%=je;
	x+=y;x%=je;
	return x;
}

long long div(long long x,long long y){
	x%=je;y%=je;
	int left=je-2;
	long long gopp=y,ret=1;
	while(left){
		if(left&1){
			ret=gop(ret,gopp);
		}
		gopp=gop(gopp,gopp);
		left >>= 1;
	}
	ret=gop(ret,x);
	return ret;
}

int main(){
    int n,k;
    long long su;
    scanf("%d %d",&n,&k);
    seq[0]=1;
    fact[0]=1;
    su=div(1,k);
    for(int i=1;i<=n;i++){
        fact[i]=gop(fact[i-1],i);
    }
    for(int i=1;i<=n;i++){
        seq[i]=gop(seq[i-1],k+1);
        if(i%2){
            su=gop(su,k);
            seq[i]=hap(seq[i],je-gop(su,div(div(div(fact[i-1],fact[i/2]),fact[i/2]),(i/2)+1)));
        }
    }
    printf("%lld\n",seq[n]);
}

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