답안 #15728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15728	2015-07-16T17:21:32 Z	cki86201	접미사 배열의 개수 (kriii3_W)	C++	46 / 46	679 ms	8896 KB

W

#include<stdio.h>

typedef long long ll;

const ll MOD = 1e9 + 7;
ll F[1000010], ans;
int n, m;

ll pw(ll x, ll y){
	ll ret = 1;
	while(y){
		if(y&1)ret = (ret * x) % MOD;
		x = (x * x) % MOD;
		y >>= 1;
	}
	return ret;
}

inline ll mul(ll x, ll y){return (x * y) % MOD;}

int main(){
	scanf("%d%d",&n,&m);
	if(m > n)m = n;
	F[0] = F[1] = 1;
	for(int i=2;i<=n;i++)F[i] = (F[i-1] * i) % MOD;
	for(int i=0;i<m;i++){
		ans += mul(mul(mul(mul(F[n], pw(F[i], MOD-2)), pw(F[n-i], MOD-2)), pw(m-i, n)), pw(-1, i));
		ans = (ans + MOD) % MOD;
	}
	printf("%lld",ans);
	return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	8896 KB	Output is correct
2	Correct	0 ms	8896 KB	Output is correct
3	Correct	0 ms	8896 KB	Output is correct
4	Correct	0 ms	8896 KB	Output is correct
5	Correct	0 ms	8896 KB	Output is correct
6	Correct	0 ms	8896 KB	Output is correct
7	Correct	0 ms	8896 KB	Output is correct
8	Correct	0 ms	8896 KB	Output is correct
9	Correct	0 ms	8896 KB	Output is correct
10	Correct	0 ms	8896 KB	Output is correct
11	Correct	0 ms	8896 KB	Output is correct
12	Correct	0 ms	8896 KB	Output is correct

Subtask #2

36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	8896 KB	Output is correct
2	Correct	8 ms	8896 KB	Output is correct
3	Correct	2 ms	8896 KB	Output is correct
4	Correct	0 ms	8896 KB	Output is correct
5	Correct	29 ms	8896 KB	Output is correct
6	Correct	79 ms	8896 KB	Output is correct
7	Correct	82 ms	8896 KB	Output is correct
8	Correct	192 ms	8896 KB	Output is correct
9	Correct	209 ms	8896 KB	Output is correct
10	Correct	422 ms	8896 KB	Output is correct
11	Correct	679 ms	8896 KB	Output is correct
12	Correct	417 ms	8896 KB	Output is correct