Submission #19291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19291	2016-02-24T06:47:05 Z	kaTkaHr	괄호 (kriii4_R)	C++14	100 / 100	260 ms	1084 KB

R

#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 1005, MM = 1000000007;

template<typename T>
T pw(T A, ll B){
  T R = 1;
  while(B){
    if( B&1 ) R = R * A;
    A = A * A; B /= 2;
  }
  return R;
}

ll rv(ll A){ 
  ll R = 1, B = MM-2;
  while(B){
    if( B&1 ) R = R * A % MM;
    A = A * A % MM; B /= 2;
  }
  return R;
}
//*
struct frac{
  ll A, B;
		frac(ll A):A(A), B(1){}
  frac(ll a, ll b){
    A = (a%MM+MM) % MM;
    B = (b%MM+MM) % MM;
  }
  frac(){A = 0, B = 1;}
  frac operator+ (const frac &l)const{
    return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
  }
  frac operator*(const frac &l)const{
    return frac(A*l.A % MM, B*l.B % MM);
  }
  frac operator/(const frac &l)const{
    return frac(A*l.B % MM, B*l.A % MM);
  }
  frac operator- (const frac &l)const{
    return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
  }
  ll v(){ return A * rv(B) % MM; }
};// */
/*
struct frac{
  ll A;
		frac(ll A):A((A%MM+MM)%MM){}
  frac(ll a, ll b){
			a = (a%MM+MM)%MM;
			b = (b%MM+MM)%MM;
			A = rv(b) * a % MM;
  }
  frac(){A = 0;}
  frac operator+ (const frac &l)const{
			return l.A + A >= MM? l.A + A - MM: l.A + A;
  }
  frac operator*(const frac &l)const{
			return l.A * A % MM;
  }
  frac operator/(const frac &l)const{
			return A * rv(l.A) % MM;
  }
  frac operator- (const frac &l)const{
			return A >= l.A? A-l.A: A-l.A + MM;
  }
  ll v(){ return A; }
};// */

int main()
{
	int N, K;
	scanf("%d%d", &N, &K);
	frac ans = 0, mul = 1, t = 0;
	for(int i = 0; i <= N/2; i++){
		ans = ans + pw(frac(K), N-i) * (mul - t);
		t = mul;
		mul = mul * (N-i) / (i+1);
	}
	printf("%lld\n", ans.v());
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	1084 KB	Output is correct
2	Correct	14 ms	1084 KB	Output is correct
3	Correct	188 ms	1084 KB	Output is correct
4	Correct	211 ms	1084 KB	Output is correct
5	Correct	216 ms	1084 KB	Output is correct
6	Correct	116 ms	1084 KB	Output is correct
7	Correct	131 ms	1084 KB	Output is correct
8	Correct	82 ms	1084 KB	Output is correct
9	Correct	33 ms	1084 KB	Output is correct
10	Correct	5 ms	1084 KB	Output is correct
11	Correct	8 ms	1084 KB	Output is correct
12	Correct	192 ms	1084 KB	Output is correct
13	Correct	182 ms	1084 KB	Output is correct
14	Correct	75 ms	1084 KB	Output is correct
15	Correct	81 ms	1084 KB	Output is correct
16	Correct	73 ms	1084 KB	Output is correct
17	Correct	237 ms	1084 KB	Output is correct
18	Correct	241 ms	1084 KB	Output is correct
19	Correct	259 ms	1084 KB	Output is correct
20	Correct	260 ms	1084 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	1084 KB	Output is correct
2	Correct	20 ms	1084 KB	Output is correct
3	Correct	42 ms	1084 KB	Output is correct
4	Correct	234 ms	1084 KB	Output is correct
5	Correct	143 ms	1084 KB	Output is correct
6	Correct	178 ms	1084 KB	Output is correct
7	Correct	117 ms	1084 KB	Output is correct
8	Correct	66 ms	1084 KB	Output is correct
9	Correct	114 ms	1084 KB	Output is correct
10	Correct	14 ms	1084 KB	Output is correct
11	Correct	203 ms	1084 KB	Output is correct
12	Correct	212 ms	1084 KB	Output is correct
13	Correct	200 ms	1084 KB	Output is correct
14	Correct	90 ms	1084 KB	Output is correct
15	Correct	113 ms	1084 KB	Output is correct
16	Correct	115 ms	1084 KB	Output is correct
17	Correct	17 ms	1084 KB	Output is correct
18	Correct	259 ms	1084 KB	Output is correct
19	Correct	259 ms	1084 KB	Output is correct
20	Correct	259 ms	1084 KB	Output is correct