Submission #15728

#	Time	Username	Problem	Language	Result	Execution time	Memory
15728		cki86201	접미사 배열의 개수 (kriii3_W)	C++98	46 / 46	679 ms	8896 KiB

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