Submission #15731

# Submission time Handle Problem Language Result Execution time Memory
15731 2015-07-17T02:32:12 Z gs14004 접미사 배열의 개수 (kriii3_W) C++14
0 / 46
0 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(-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 Incorrect 0 ms 8896 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -