Submission #20087

# Submission time Handle Problem Language Result Execution time Memory
20087 2016-02-25T10:47:37 Z gs14004 괄호 (kriii4_R) C++14
100 / 100
228 ms 48596 KB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint fact[2000005];
lint cat[2000005];
lint dp[2000005];

lint ipow(lint x, lint p){
    lint ret = 1, piv = x % mod;
    while(p){
        if(p&1) ret *= piv;
        piv *= piv;
        ret %= mod;
        piv %= mod;
        p >>= 1;
    }
    return ret;
}
 
int main(){
	int n, k;
	cin >> n >> k;
	fact[0] = 1;
	for(int i=1; i<=n; i++){
		fact[i] = fact[i-1] * i % mod;
	}
	for(int i=0; i<=n/2; i++){
		cat[i] = fact[2*i] * ipow(fact[i+1] * fact[i], mod - 2) % mod;
	}
	dp[0] = 1;
	for(int i=1; i<=n; i++){
		if(i%2 == 0){
			dp[i] = dp[i-1] * (k+1) % mod;
		}
		else{
			dp[i] = dp[i-1] * (k+1) % mod - cat[i/2] * ipow(k, i/2) % mod + mod;
			dp[i] %= mod;
		}
	}
	cout << dp[n];
}
# Verdict Execution time Memory Grader output
1 Correct 60 ms 48596 KB Output is correct
2 Correct 14 ms 48596 KB Output is correct
3 Correct 167 ms 48596 KB Output is correct
4 Correct 184 ms 48596 KB Output is correct
5 Correct 186 ms 48596 KB Output is correct
6 Correct 105 ms 48596 KB Output is correct
7 Correct 118 ms 48596 KB Output is correct
8 Correct 78 ms 48596 KB Output is correct
9 Correct 29 ms 48596 KB Output is correct
10 Correct 8 ms 48596 KB Output is correct
11 Correct 9 ms 48596 KB Output is correct
12 Correct 167 ms 48596 KB Output is correct
13 Correct 161 ms 48596 KB Output is correct
14 Correct 69 ms 48596 KB Output is correct
15 Correct 74 ms 48596 KB Output is correct
16 Correct 67 ms 48596 KB Output is correct
17 Correct 205 ms 48596 KB Output is correct
18 Correct 215 ms 48596 KB Output is correct
19 Correct 227 ms 48596 KB Output is correct
20 Correct 228 ms 48596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 57 ms 48596 KB Output is correct
2 Correct 16 ms 48596 KB Output is correct
3 Correct 37 ms 48596 KB Output is correct
4 Correct 198 ms 48596 KB Output is correct
5 Correct 124 ms 48596 KB Output is correct
6 Correct 147 ms 48596 KB Output is correct
7 Correct 108 ms 48596 KB Output is correct
8 Correct 57 ms 48596 KB Output is correct
9 Correct 99 ms 48596 KB Output is correct
10 Correct 14 ms 48596 KB Output is correct
11 Correct 175 ms 48596 KB Output is correct
12 Correct 175 ms 48596 KB Output is correct
13 Correct 174 ms 48596 KB Output is correct
14 Correct 83 ms 48596 KB Output is correct
15 Correct 102 ms 48596 KB Output is correct
16 Correct 103 ms 48596 KB Output is correct
17 Correct 13 ms 48596 KB Output is correct
18 Correct 224 ms 48596 KB Output is correct
19 Correct 224 ms 48596 KB Output is correct
20 Correct 227 ms 48596 KB Output is correct