답안 #15732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15732	2015-07-17T02:32:50 Z	gs14004	접미사 배열의 개수 (kriii3_W)	C++14	46 / 46	686 ms	8896 KB

W

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long lint;
const int mod = 1e9 + 7;

lint p(lint a, int b){
	lint ret = 1, piv = a;
	while(b){
		if(b&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		b >>= 1;
	}
	return ret;
}

lint fac[1000005];

int main(){
	int n, m;
	scanf("%d %d",&n,&m);
	m = min(n, m);
	fac[0] = 1;
	for(int i=1; i<=n; i++){
		fac[i] = (1ll * fac[i-1] * i) % mod;
	}
	lint ret = 0;
	for(int i=0; i<m; i++){
		lint comb = ((1ll * fac[n] * p(fac[i], mod - 2) % mod)  * p(fac[n-i], mod - 2) % mod);
		comb *= p(mod -1, i);
		comb %= mod;
		comb *= p(m - i, n);
		comb %= mod;
		ret += comb;
		ret %= mod;
	}
	printf("%lld",ret);
}

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	4 ms	8896 KB	Output is correct
4	Correct	0 ms	8896 KB	Output is correct
5	Correct	33 ms	8896 KB	Output is correct
6	Correct	80 ms	8896 KB	Output is correct
7	Correct	84 ms	8896 KB	Output is correct
8	Correct	194 ms	8896 KB	Output is correct
9	Correct	215 ms	8896 KB	Output is correct
10	Correct	429 ms	8896 KB	Output is correct
11	Correct	686 ms	8896 KB	Output is correct
12	Correct	419 ms	8896 KB	Output is correct