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

R

//*
#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;
}
//*/

Subtask #1

8.0 / 8.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

Subtask #2

92.0 / 92.0

#	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