yukicoder 391 - CODING WAR

包除原理は便利だなぁ！☺️

問題

n人の競技プログラマとm個の競技プログラミング問題がある
・各競技プログラマはどれかの問題を1問だけ解く
・各問題は必ず1人以上のプログラマによって解かれないといけない
・同じ問題を担当するプログラマが複数いてもいい
各プログラマに担当させる問題の組み合わせであって、これらの条件を全て満たすようなものの個数を求めよ

1 <= n <= 10^12
1 <= m <= 10^5

解法

f(k): 担当者がいない問題がk問以上あるような担当者の決め方の個数
とすると答えは包除原理より
Σ f(k) * (-1)^k (0 <= k <= m)
となる
f(k)はm問のうちどのk問を担当者不在にするかでmCk通りあり、その上でn人が残りm-k問のどれかを解くわけだから
f(k) = mCk * (m-k)^n

実装

mop = modpow

#define int long long

int n, m, res;

const int MAXS = 200200;
ll fact[MAXS+1], factr[MAXS+1], inv[MAXS+1];
ll comb(ll n, ll r) {
	if (fact[0]==0) {
		fact[0] = factr[0] = inv[1] = 1;
		for (int i=2; i<=MAXS; i++) inv[i] = inv[mod%i] * (mod-mod/i) %mod;
		for (int i=1; i<=MAXS; i++) fact[i] = fact[i-1]*i %mod, factr[i] = factr[i-1]*inv[i] %mod;
	}
	if (r<0 || n<r) return 0;
	return fact[n]*factr[r] %mod *factr[n-r] %mod;
}

signed main() {
	cin >> n >> m;
	rep(i,m+1) {
		int p = comb(m,i) * mop(m-i,n) %mod;
		(res += p * (i%2 ? -1 : 1)) %= mod;
	}
	(res += mod) %= mod;
	cout << res << endl;
}

https://yukicoder.me/problems/no/391