ARC009 C - 高橋君、24歳

問題ページ
C - 高橋君、24歳

考えたこと

• 正しく手紙をいれた人のパターンはC(N,K)でO(K)で求まるので問題ない
• 問題は誤ったK人の方が何パターンあるか
• 組み合わせを頑張ってO(1)とか考えるけど思い浮かばない
• 樹形図を書いて小さいケースについて実験する
• k=5のとき B-A-… だと2パターンだけど B-C-… と置かれてると3パターン
• 前に置かれてた状況で後ろが何通りあるか結構変わるしO(1)が出来る気がしない
• 後ろのうち置いてない個数が何個あるかを持ったりしたい気持ちになったけどO(K^2)で不可能
  -----解説を見た-----
• モンモール数

完全順列のことは知っていたはずなのに完全に頭から消えていた…

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const ll MOD = 1777777777;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll combi(ll N_, ll C_) {
  const int NUM_=800001;
  static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
  auto binpow = [&](ll x, ll e) -> ll {
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    return a % MOD;
  };
  if (fact[0]==0) {
    fact[0] = factr[0] = inv[0] = 1;
    FOR(i, 1, NUM_+1) {
      fact[i] = fact[i-1] * i;
      inv[i] = binpow(i, MOD-2);
      factr[i] = factr[i-1] * inv[i];
    }
  }
  if(C_<0 || C_>N_) return 0;
  // 前計算 O(max(N,K)log(mod)) クエリ O(1)
  // return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;
  // 前計算 O(max(N,K)log(mod)) クエリ O(K)
  ll ret = 1;
  for(;C_>0;N_--,C_--) (ret *= N_%MOD) %= MOD, (ret *= inv[C_]) %= MOD;
  return ret;
}

signed main(void)
{
  int n, k;
  cin >> n >> k;

  if(k == 1) {
    cout << 0 << endl;
    return 0;
  }

  // モンモール数
  int a = 0, b = 1;
  FOR(i, 3, k+1) {
    int nxt = (i-1)*(a+b)%MOD;
    a = b, b = nxt;
  }

  cout << combi(n, k) * b % MOD << endl;

  return 0;
}