ARC 009 C

C - 高橋君、24歳

問題概要

Nコのポストに手紙を届ける。Kコの手紙だけ正しくないポストに届き、すべてのポストに手紙が1コずつ届く。このとき、ポストと手紙の対応関係は mod 1777777777 (素数) で何通りか。(2 <= N <= 1e18, 2 <= K <= 1e6)

• ヒント1

正しく届かない手紙・ポストの集合を固定して考える。

• ヒント2

正しく届かない手紙・ポストの集合は K なので、まずは N = K の場合で解くことを考える。
すると、ポスト・手紙がそれぞれ K コあり、どれも正しく届かない届き方のが何通りあるのか計算する問題になる。
これは、正しく届く手紙の集合に関する包除原理で計算することができる。

#define N 2000000
ll inv[N], fact[N], ifact[N], be[N];
 
ll comb(ll a, ll b){
	return fact[a+b]*ifact[a]%mod*ifact[b]%mod;
}
 
ll comb_nk(ll n, ll k){
	return comb(n-k, k);
}
 
ll pow_mod(ll a, ll r, ll m){
	ll x = 1;
	while(r){
		if(r&1) (x*=a)%=m;
		(a*=a)%=m;
		r>>=1;
	}
	return x;
}
 
void init_fact(ll n = N){
    inv[1] = 1;
    for(int i = 2; i < n; i++) inv[i] = inv[mod%i] * (mod - mod/i) % mod;
	fact[0] = ifact[0] = 1;
	for(int i = 1; i < n; i++){
		fact[i] = (fact[i-1]*i)%mod;
		ifact[i]=(ifact[i-1]*inv[i])%mod;
	}
}

int main(){
	init_fact();
	ll n, k;
	cin>>n>>k;
	ll res = 0;
	rep(i, k+1){
		(res+=fact[k-i]*comb_nk(k, i)%mod*(i%2?-1:1))%=mod;
	}
	(res*=ifact[k])%=mod;
	rep(i, k) (res*=(n-i)%mod)%=mod;
	res += mod;
	cout<<res%mod<<endl;
	return 0;
}