2021/04/02 - Lru Room

概略

新卒の方々が入ってきてフレッシュさを感じつつ仕事の増加を感じる日々になってきた. 去年自分はあんなにまでフレッシュだったのだろうか?

そんなこんなで今日は時間がなかったので数カ月ぶりに弁当というものを買って食べたが, 1分半でカツカレーが出来る技術力ってすごいよなぁとかいいつつ全然足りないのを感じる. やはり大量に食べる人間だと自炊のほうが多少コスパは良いのだろうか. 全然足りないので結局お菓子をつまみながらこれを書いている. チーズとワインも開けちゃう.

今日の競プロ

ランダム選択で

今日は ABC167E Colorful Blocks

1列でn個のブロックのm色での塗り方で同色が隣り合うところがk組以下になるような並べ方.

x組ピッタリ隣り合うところが同色になる物が出来るパターン数は, 各々が左隣と色の異なるようにn-i個のブロックをm色で塗る塗り方の総数に, どこが組みになるかの組み合わせ数を掛けた物と同じ.

各々が左隣と色の異なるようにn-x個のブロックをm色で塗る塗り方は左端がm色, それ以外は左隣の1色を除くm-1色から選べばよいので,

$M \times (M - 1)^{n - x - 1}$

どこが組になるのかの組み合わせ数は, ブロックとブロックの隙間の数n-1からx個選ぶ組み合わせ数と同じなので,

${}_{n-1} \mathrm{C}_x = \frac{(n-1)!}{x!(n-x-1)!}$

modが素数指定なのでモジュラ逆数が使える.

$\frac{(n-1)!}{x!(n-x-1)!} = (n-1)! \times (x)!^{-1} \times (n-x-1)!^{-1}$

ここまで分かれば $0 \leq x \leq k$ の範囲を計算して合算するだけ.

$O(N \log MOD + K \log N)$

submit result

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// mod計算utils
template <typename Head>
ll modprod(Head head){return head;}
template <typename Head, typename... Tail>
ll modprod(Head head, Tail... tail) {
  return (head * modprod(tail...)) % MOD;
}

template <typename Head>
ll modsum(Head head){return head;}
template <typename Head, typename... Tail>
ll modsum(Head head, Tail... tail) {
  return (head + modsum(tail...)) % MOD;
}

ll modpow(ll x, ll p) {
  ll a = 1;
  while(p > 0) {
    if(p % 2 == 1) a = modprod(a, x);
    x = modprod(x, x);
    p /= 2;
  }
  return a;
}

ll modinv(ll x){
  return modpow(x, MOD-2);
}

int main(){
  ll n, m, k;
  cin >> n >> m >> k;

  // 階乗とその逆数を計算しておく
  vector<ll> fact(n+1), invfact(n+1);
  fact[0] = 1; invfact[0] = 1;
  for(int i=1; i<=n; i++) {
    fact[i] = modprod(i, fact[i-1]);
    invfact[i] = modinv(fact[i]);
  }

  ll ans = 0;
  for(int i=0; i<=k; i++) {
    // 計算式通りの計算をするだけ
    ll pat = modprod(m, modpow(m-1, n-i-1), fact[n - 1], invfact[i], invfact[n - i - 1]);
    ans = modsum(ans, pat);
  }
  cout << ans << endl;
}