Submission #21289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21289	2017-04-12T12:45:45 Z	suzy	괄호 (kriii4_R)	C++11	100 / 100	483 ms	16740 KB

R

#include <stdio.h>

#define MOD 1000000007LL

typedef long long lli;

lli d[1000001], c[1000001];

lli pw(lli n, lli x) {
	if(x==0) return 1;
	if(x%2) return n*pw(n,x-1)%MOD;
	else { lli ret=pw(n,x/2); return ret*ret%MOD; }
}

int main() {
	c[1]=1;
	for(lli i=2;i<=1000000;i++) {
		lli aa=(2*i-1)*(2*i)%MOD;
		lli bb=pw(i*(i+1)%MOD,MOD-2);
		c[i]=c[i-1]*aa%MOD*bb%MOD;
	}
	lli n, k;
	scanf("%lld %lld",&n,&k);
	d[1]=k;
	for(lli i=2;i<=n;i++) {
		if(i%2) d[i]=(d[i-1]*(k+1)%MOD-c[(i-1)/2]*pw(k,(i-1)/2)%MOD+MOD)%MOD;
		else d[i]=d[i-1]*(k+1)%MOD;
	}
	printf("%lld\n",d[n]);
	return 0;
}

Compilation message

R.cpp: In function 'int main()':
R.cpp:23:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&k);
                          ^

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	386 ms	16740 KB	Output is correct
2	Correct	356 ms	16740 KB	Output is correct
3	Correct	443 ms	16740 KB	Output is correct
4	Correct	443 ms	16740 KB	Output is correct
5	Correct	456 ms	16740 KB	Output is correct
6	Correct	406 ms	16740 KB	Output is correct
7	Correct	409 ms	16740 KB	Output is correct
8	Correct	393 ms	16740 KB	Output is correct
9	Correct	373 ms	16740 KB	Output is correct
10	Correct	359 ms	16740 KB	Output is correct
11	Correct	353 ms	16740 KB	Output is correct
12	Correct	443 ms	16740 KB	Output is correct
13	Correct	439 ms	16740 KB	Output is correct
14	Correct	386 ms	16740 KB	Output is correct
15	Correct	393 ms	16740 KB	Output is correct
16	Correct	393 ms	16740 KB	Output is correct
17	Correct	463 ms	16740 KB	Output is correct
18	Correct	459 ms	16740 KB	Output is correct
19	Correct	476 ms	16740 KB	Output is correct
20	Correct	476 ms	16740 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	389 ms	16740 KB	Output is correct
2	Correct	356 ms	16740 KB	Output is correct
3	Correct	369 ms	16740 KB	Output is correct
4	Correct	459 ms	16740 KB	Output is correct
5	Correct	423 ms	16740 KB	Output is correct
6	Correct	443 ms	16740 KB	Output is correct
7	Correct	396 ms	16740 KB	Output is correct
8	Correct	383 ms	16740 KB	Output is correct
9	Correct	409 ms	16740 KB	Output is correct
10	Correct	353 ms	16740 KB	Output is correct
11	Correct	446 ms	16740 KB	Output is correct
12	Correct	446 ms	16740 KB	Output is correct
13	Correct	453 ms	16740 KB	Output is correct
14	Correct	393 ms	16740 KB	Output is correct
15	Correct	403 ms	16740 KB	Output is correct
16	Correct	409 ms	16740 KB	Output is correct
17	Correct	376 ms	16740 KB	Output is correct
18	Correct	473 ms	16740 KB	Output is correct
19	Correct	476 ms	16740 KB	Output is correct
20	Correct	483 ms	16740 KB	Output is correct