제출 #15732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15732		gs14004	접미사 배열의 개수 (kriii3_W)	C++14	46 / 46	686 ms	8896 KiB

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 / 10
• Subtask 2: 36 / 36