oj.uz

답안 #19961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19961 2016-02-25T07:50:42 Z yukariko 괄호 (kriii4_R) C++14
0 / 100
 238 ms 25160 KB 
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

int N, M;

long long cache[1000001];

long long mod_exp(long long a,long long b,long long c)
{
	a%=c;
	if(b==0)return 1;
	if(b==1)return a;
	if(b&1) return (a*mod_exp((a*a)%c,(b-1)/2,c))%c;
	return mod_exp((a*a)%c,b/2,c);
}

long long mod_div(long long a, long long b)
{
	return (a * mod_exp(b, MOD-2, MOD)) % MOD;
}

long long solve(int pos, int left)
{
	if(left < 0)
		return 0;
	if(pos == N)
		return 1;

	long long ans = (solve(pos + 1, left - 1));
	ans = (ans + solve(pos + 1, left + 1) * M) % MOD;
	return ans;
}

long long pow2[1000001];
long long nCm[1000001];

int main()
{
	scanf("%d%d", &N, &M);

	pow2[1] = 1;
	for(int i=2; i <= N; i++)
		pow2[i]= (pow2[i-1] * M) % MOD;

	nCm[0] = 1;
	nCm[1] = 1;
	for(int i=2; i <= N/2; i++)
	{
		long long n = i-1;
		nCm[i] = (nCm[i-1] * (n * 2 + 1)) % MOD;
		nCm[i] = (nCm[i] * (n * 2 + 2)) % MOD;
		nCm[i] = mod_div(nCm[i], (n + 1) * (n + 2) % MOD );
	}

	cache[0] = 1;
	cache[1] = M;
	cache[2] = M * (M+1);
	for(int i=3; i < N; i+=2)
	{
		cache[i] = ((cache[i-1] * (M+1) % MOD) - (pow2[(i+1)/2] * nCm[i/2] % MOD) + MOD) % MOD;
		cache[i+1] = cache[i] * (M+1) % MOD;
	}

	printf("%lld\n", cache[N]);
	return 0;
}

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 25160 KB Output is correct
2 Incorrect 49 ms 25160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -