답안 #19663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19663 2016-02-25T04:20:23 Z tonyjjw 괄호 (kriii4_R) C++14
8 / 100
294 ms 16904 KB
//*
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#define all(A) (A).begin(), (A).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MN = 1000000+10;
const ll mod = 1000000007;

ll fact[MN];
ll inv[MN];

ll pow(ll a,ll p){
	ll r=1;
	while(p>0){
		if(p&1)r=r*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return r;
}

ll comb(ll n,ll r){
	return fact[n]*inv[r]%mod*inv[n-r]%mod;
}
ll inverse(ll a){
	return pow(a,mod-2);
}

int main(){
	int N,K;
	scanf("%d%d",&N,&K);
	fact[0]=1;
	for(int i=1;i<MN;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	for(int i=0;i<MN;i++){
		inv[i]=inverse(fact[i]);
	}
	ll ans=0;
	for(int i=0;2*i<=N;i++){
		ll v;
		if(i==0){
			v=1;
		}
		else{
			v=comb(N,i)-comb(N,i-1);
		}
		v*=pow(K,N-i);
		v%=mod;
		ans+=v;
		ans%=mod;
	}
	if(ans<0)ans+=mod;
	printf("%lld\n",ans);
	return 0;
}
//*/
# 결과 실행 시간 메모리 Grader output
1 Correct 266 ms 16904 KB Output is correct
2 Correct 260 ms 16904 KB Output is correct
3 Correct 281 ms 16904 KB Output is correct
4 Correct 284 ms 16904 KB Output is correct
5 Correct 289 ms 16904 KB Output is correct
6 Correct 271 ms 16904 KB Output is correct
7 Correct 277 ms 16904 KB Output is correct
8 Correct 267 ms 16904 KB Output is correct
9 Correct 260 ms 16904 KB Output is correct
10 Correct 259 ms 16904 KB Output is correct
11 Correct 260 ms 16904 KB Output is correct
12 Correct 282 ms 16904 KB Output is correct
13 Correct 280 ms 16904 KB Output is correct
14 Correct 265 ms 16904 KB Output is correct
15 Correct 262 ms 16904 KB Output is correct
16 Correct 262 ms 16904 KB Output is correct
17 Correct 289 ms 16904 KB Output is correct
18 Correct 284 ms 16904 KB Output is correct
19 Correct 291 ms 16904 KB Output is correct
20 Correct 294 ms 16904 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 271 ms 16904 KB Output isn't correct
2 Halted 0 ms 0 KB -