Submission #19984

#	Time	Username	Problem	Language	Result	Execution time	Memory
19984		gs12117	동전 (kriii4_E)	C++98	0 / 100	0 ms	8904 KiB

D

#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 / 5
• Subtask 2: 0 / 95