Submission #15732

# Submission time Handle Problem Language Result Execution time Memory
15732 2015-07-17T02:32:50 Z gs14004 접미사 배열의 개수 (kriii3_W) C++14
46 / 46
686 ms 8896 KB
#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);
}
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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