AtCoder Regular Contest 009 C - 高橋君、24歳
解法
「0 から K-1 がバラバラ, 残りは揃っている」の場合の数が分かれば, 後は答えを comb[N][K] 倍するだけです。comb[N][K] はおよそ O(K log K) で求めることができるので, 問題は「」の中身の場合の数です。
これは, 包除原理で求めることが出来ます。
0 個以上重なっているのがある場合の数は K! 通り,
1 個以上重なっているのがある場合の数は comb[K][1] * (K-1)! = K! 通り,
2 個以上重なっているのがある場合の数は comb[K][2] * (K-2)! = K!/2! 通り,
3 個以上重なっているのがある場合の数は comb[K][3] * (K-3)! = K!/3! 通り, ...
と続きます。答えは K! - K! + K!/2! - K!/3! + ... となるので, これを計算しましょう。
typedef unsigned long long ull; const ull MOD = 1777777777; ull mod_pow(ull x, ull p, ull MOD) { ull a = 1; while (p) { if (p%2) a = a*x%MOD; x = x*x%MOD; p/=2; } return a; } // mod_inverse ull mod_inverse(ull a, ull m) { return mod_pow(a, MOD-2, m); } ull nCr(ull n, ull r) { ull ret = 1; for (ull i = 0; i < r; i++) (ret *= (n-i)%MOD) %= MOD; for (ull i = 1; i <= r; i++) (ret *= mod_inverse(i, MOD)) %= MOD; return ret; } ull calc(ull K) { ull p = 1; for (ull i = 1; i <= K; i++) (p *= i) %= MOD; ull ret = 0; for (ull i = 2; i <= K; i++) { (p *= mod_inverse(i, MOD)) %= MOD; if (i%2==0) (ret += p) %= MOD; else (ret += MOD-p) %= MOD; } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); ull N, K; cin >> N >> K; ull ans = calc(K); (ans *= nCr(N, K)) %= MOD; cout << ans << endl; return 0; }