oj.uz

Submission #19984

# Submission time Handle Problem Language Result Execution time Memory
19984 2016-02-25T08:08:40 Z gs12117 동전 (kriii4_E) C++
0 / 100
 0 ms 8904 KB 
#include<stdio.h>
int n,m;
long long int dp[1001000];
int mod=1000000007;
int mpow(int x,int y){
	if(y==0)return 1;
	long long int r=mpow(x,y/2);
	r*=r;
	r%=mod;
	if(y%2==1){
		r*=x;
		r%=mod;
	}
	return r;
}
int minv(int x){
	return mpow(x,mod-2);
}
int main(){
	int i;
	long long int cat;
	scanf("%d%d",&n,&m);
	dp[0]=1;
	cat=1;
	for(i=0;i<n;i++){
		dp[i+1]=dp[i]*(m+1);
		dp[i+1]%=mod;
		if(i%2==0){
			dp[i+1]+=mod-cat;
			dp[i+1]%=mod;
			cat*=i+1;
			cat%=mod;
			cat*=i+2;
			cat%=mod;
			cat*=minv(i/2+1);
			cat%=mod;
			cat*=minv(i/2+2);
			cat%=mod;
			cat*=m;
			cat%=mod;
		}
	}
	printf("%lld",dp[n]);
}

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 95.0

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