Submission #20150

# Submission time Handle Problem Language Result Execution time Memory
20150 2016-02-28T15:00:14 Z tonyjjw 괄호 (kriii4_R) C++14
100 / 100
353 ms 16708 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 mpow(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 mpow(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*=mpow(K,N-i);
        v%=mod;
        ans+=v;
        ans%=mod;
    }
    if(ans<0)ans+=mod;
    printf("%lld\n",ans);
    return 0;
}
//*/
# Verdict Execution time Memory Grader output
1 Correct 277 ms 16708 KB Output is correct
2 Correct 263 ms 16708 KB Output is correct
3 Correct 327 ms 16708 KB Output is correct
4 Correct 331 ms 16708 KB Output is correct
5 Correct 333 ms 16708 KB Output is correct
6 Correct 292 ms 16708 KB Output is correct
7 Correct 301 ms 16708 KB Output is correct
8 Correct 289 ms 16708 KB Output is correct
9 Correct 270 ms 16708 KB Output is correct
10 Correct 253 ms 16708 KB Output is correct
11 Correct 257 ms 16708 KB Output is correct
12 Correct 328 ms 16708 KB Output is correct
13 Correct 324 ms 16708 KB Output is correct
14 Correct 285 ms 16708 KB Output is correct
15 Correct 280 ms 16708 KB Output is correct
16 Correct 280 ms 16708 KB Output is correct
17 Correct 341 ms 16708 KB Output is correct
18 Correct 347 ms 16708 KB Output is correct
19 Correct 353 ms 16708 KB Output is correct
20 Correct 352 ms 16708 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 278 ms 16708 KB Output is correct
2 Correct 265 ms 16708 KB Output is correct
3 Correct 270 ms 16708 KB Output is correct
4 Correct 340 ms 16708 KB Output is correct
5 Correct 310 ms 16708 KB Output is correct
6 Correct 319 ms 16708 KB Output is correct
7 Correct 302 ms 16708 KB Output is correct
8 Correct 282 ms 16708 KB Output is correct
9 Correct 297 ms 16708 KB Output is correct
10 Correct 263 ms 16708 KB Output is correct
11 Correct 331 ms 16708 KB Output is correct
12 Correct 327 ms 16708 KB Output is correct
13 Correct 327 ms 16708 KB Output is correct
14 Correct 291 ms 16708 KB Output is correct
15 Correct 299 ms 16708 KB Output is correct
16 Correct 300 ms 16708 KB Output is correct
17 Correct 260 ms 16708 KB Output is correct
18 Correct 353 ms 16708 KB Output is correct
19 Correct 349 ms 16708 KB Output is correct
20 Correct 341 ms 16708 KB Output is correct