답안 #19965

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

using namespace std;

const long long MOD = 1000000007;

long long N, M;

long long cache[1000005];

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[1000005];
long long nCm[1000005];

int main()
{
	scanf("%lld%lld", &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) % MOD;
	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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 25160 KB Output is correct
2 Correct 49 ms 25160 KB Output is correct
3 Correct 583 ms 25160 KB Output is correct
4 Correct 655 ms 25160 KB Output is correct
5 Correct 668 ms 25160 KB Output is correct
6 Correct 366 ms 25160 KB Output is correct
7 Correct 416 ms 25160 KB Output is correct
8 Correct 278 ms 25160 KB Output is correct
9 Correct 115 ms 25160 KB Output is correct
10 Correct 28 ms 25160 KB Output is correct
11 Correct 31 ms 25160 KB Output is correct
12 Correct 591 ms 25160 KB Output is correct
13 Correct 563 ms 25160 KB Output is correct
14 Correct 246 ms 25160 KB Output is correct
15 Correct 265 ms 25160 KB Output is correct
16 Correct 240 ms 25160 KB Output is correct
17 Correct 729 ms 25160 KB Output is correct
18 Correct 752 ms 25160 KB Output is correct
19 Correct 790 ms 25160 KB Output is correct
20 Correct 795 ms 25160 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 25160 KB Output is correct
2 Correct 67 ms 25160 KB Output is correct
3 Correct 143 ms 25160 KB Output is correct
4 Correct 719 ms 25160 KB Output is correct
5 Correct 447 ms 25160 KB Output is correct
6 Correct 548 ms 25160 KB Output is correct
7 Correct 385 ms 25160 KB Output is correct
8 Correct 215 ms 25160 KB Output is correct
9 Correct 380 ms 25160 KB Output is correct
10 Correct 50 ms 25160 KB Output is correct
11 Correct 627 ms 25160 KB Output is correct
12 Correct 655 ms 25160 KB Output is correct
13 Correct 621 ms 25160 KB Output is correct
14 Correct 294 ms 25160 KB Output is correct
15 Correct 363 ms 25160 KB Output is correct
16 Correct 363 ms 25160 KB Output is correct
17 Correct 61 ms 25160 KB Output is correct
18 Correct 791 ms 25160 KB Output is correct
19 Correct 796 ms 25160 KB Output is correct
20 Correct 784 ms 25160 KB Output is correct