ferinの競プロ帳

競プロについてのメモ

codeforces #428 div2 D

競技プログラミング Codeforces

問題ページ
Problem - D - Codeforces

考えたこと

  • 部分列を全列挙とかそういう方向は不可能そうなので各要素が含まれる部分列の回数とかそういう方向で考える
  • gcdがiとなるような部分列について考える
  • (部分列の長さの和)*i がこんな部分列のスコアになる
  • m要素からk要素を選ぶとgcdがiになるとすると部分列の長さの和は sum(k*C(m,k)) になる
  • 問題はどんなk要素を選び出してもgcdがiになるようなm要素が厳しい
  • gcdがiより大きいパターンが存在しうるのでどうすれば列挙できるのかよくわからない
  • iの候補がO(max(a))なのでsum(k*C(m,k))を求めるのにさらにO(n)かけたりしたら確実にTLE
    -----解説を見た-----
  • gcdがiより大きいパターンに関しては包除原理の要領でやればいける
  • sum_{k=1}^m (k*C(m,k)) = m2^(m-1) で簡単に求まる
  • f(i) = (iが約数になる数の個数) とする
  • g(i) = f(i)2^(f(i)-1) - sum_{jはiの倍数} g(j)
  • g(i) について大きい方から順に求めていけば引くべきg(j)はすでに求まっている
  • O(max(a) + max(a)/2 + max(a)/3 + … + 1) = O(max(a)log(max(a)))
  • f(i) を求める部分は O(nsqrt(max(a))) で求まる

学び

  • gcdがiのグループについて考えるのは割と汎用性がありそう
for(int i=maxa; i>=0; --i) {
  // gcdがiのグループについて計算
  for(int j=i*2; j<=maxa; j+=i) // gcdがjのグループの分を引く
}
  • sum_{k=1}^m (k*C(m,k)) = m2^(m-1) になる
  • sum(C(n,k)) みたいなのがあったらもっと簡単に書けないか調べてもよさそう

ソースコード

#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 int MOD = 1000000007;

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};

int a[200010];
int cnt[1000010], pow2[1000010], dp[1000010];
signed main(void)
{
  int n;
  scanf("%lld", &n);
  REP(i, n) scanf("%lld", &a[i]);

  REP(i, n) {
    for(int j=1; j*j<=a[i]; ++j) {
      if(a[i]%j==0) {
        cnt[j]++;
        if(j*j != a[i]) cnt[a[i]/j]++;
      }
    }
  }

  pow2[0] = 1;
  FOR(i, 1, 1000001) {
    pow2[i] = pow2[i-1]*2;
    if(pow2[i] >= MOD) pow2[i] -= MOD;
  }

  // gcdがiのグループのサイズの和
  int ret = 0;
  // gcdがiのグループについて
  for(int i=1000000; i>=2; --i) {
    dp[i] = cnt[i]*pow2[cnt[i]-1]%MOD;
    if(dp[i]==0) continue;
    // iの倍数のグループはもう既に数えているので重複しないよう引く
    for(int j=i*2; j<=1000000; j+=i) dp[i] -= dp[j];
    dp[i] = (dp[i]%MOD+MOD)%MOD;
    (ret += dp[i]*i) %= MOD;
  }

  cout << ret << endl;

  return 0;
}

codeforces #428 div2 C. Journey

競技プログラミング Codeforces

問題ページ
Problem - C - Codeforces

考えたこと

  • s8pcで見た D - Driving on a Tree
  • 1頂点から求めればいいだけなのでもっと簡単
  • 頂点1を根とした木について考える
  • 止まる頂点は葉以外ありえない
  • 葉までの距離とその葉にたどりつく確率を求めれば期待値が求まる
  • 葉までの距離はdfsすればいいだけなので簡単
  • 頂点vにたどり着く可能性がpで頂点vの子がr_1,r_2,…,r_kならこれらの子にたどり着く確率はp/kになる
  • 根から順番に探索していけばいいのでこれもdfsでできる
#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 int MOD = 1000000007;

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};

double dp[100010];
int dist[100010];
VI g[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].PB(b);
    g[b].PB(a);
  }

  function<void(int,int,int,double)>
  dfs = [&](int v, int p, int d, double prob) {
    dist[v] = d;
    dp[v] = prob;
    for(int &to: g[v]) if(to != p) {
      int num = (p==-1?g[v].size():g[v].size()-1);
      dfs(to, v, d+1, prob/num);
    }
  };
  dfs(0, -1, 0, 1);

  double ret = 0;
  FOR(i, 1, n) if(g[i].size() == 1) ret += dist[i]*dp[i];
  cout << fixed << setprecision(9) << ret << endl;

  return 0;
}

codeforces #428 div2 B. Game of the Rows

競技プログラミング Codeforces

問題ページ
Problem - B - Codeforces

考えたこと

  • 二人席が2n個、四人席がn個あると考えればよさそう
  • ぴったり座れるときに座らない方がいいことはなさそう
  • 二人席と四人席のどちらを先に埋めるべきか
  • 四人席*1より二人席*2の方があとあとぴったり埋められるのが増えそうだし四人席を先に埋めるべきっぽい
  • 4人席を埋められるだけ埋めたあと2人席を埋めるみたいなのを書く
  • sampleを見ると2人席が埋まって4人席が空いてるときに4人以下が来るみたいなパターンがある
  • 4人席に2人を座らせたら4人席が減って1人席が増えると考えることにした
  • 4人席を埋められるだけ埋める
    • 4人席が残っていたらそのグループの残り人数は3人以下 (ピッタリ埋められる) > (4人席) > (2人席) > (1人席) の優先度で埋める
    • 4人席が残っていなかったら2人席で埋める
  • 出したら落ちる
  • コーナーケースが無限にありそうだけど見つからない
    -----解説を見た-----
  • 2人を1人席2つで座らせる場合が抜けていた…
  • 4の倍数人は絶対にぴったり座らせられる
  • 各グループで人数が3人以下になるまで座らせておく
  • a[i] = 1, a[i] = 2, a[i] = 3 で場合分けして座らせる

コーナーケースになりそうなのとして下のとか

3 11
2 2 2 2 2 2 2 2 2 2 2

C - スキーリフトの相乗りを思い出した
場合分けゲー苦手すぎる

#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 int MOD = 1000000007;

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};

signed main(void)
{
  int n, k;
  cin >> n >> k;
  int two = n*2, four = n, one = 0;
  VI a(k);
  REP(i, k) cin >> a[i];

  // a[i]で4以上の分を埋める
  REP(i, k) {
    if(four > a[i]/4) {
      four -= a[i]/4;
      a[i] %= 4;
    } else {
      a[i] -= four*4;
      four = 0;
    }

    if(a[i] < 4) continue;
    two -= a[i]/2;
    a[i] %= 2;
  }

  // 各グループは4人以下
  REP(i, k) {
    if(a[i] == 3) {
      if(one >= 3) one -= 3;
      else if(four) four--;
      else if(two >= 2) two -= 2;
      else {
        cout << "NO" << endl;
        return 0;
      }
    } else if(a[i] == 2) {
      if(two) two--;
      else if(four) four--, one++;
      else if(one >= 2) one -= 2;
      else {
        cout << "NO" << endl;
        return 0;
      }
    } else if(a[i] == 1) {
      if(one) one--;
      else if(four) four--, two++;
      else if(two) two--;
      else {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  cout << "YES" << endl;

  return 0;
}

SRM681 div1 easy FleetFunding

競技プログラミング SRM

考えたこと

  • つくる数を決め打ったときにそれを実現できるかについて単調性がありそうなのでにぶたんができそう
  • 二分探索部分でO(log(nm))
  • 判定部分をどうすればいいか
  • 区間と言われたので終端でソートする
  • 終端が遅いものをできるだけ残しておくと後半にも使えてうれしい
  • 終端が早いものから順番に消費していく貪欲で判定ができそう
  • O(mn)で判定できるので問題なさそう
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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 int MOD = 1000000007;

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};

class FleetFunding {
   public:
   int maxShips(int m, vector <int> k, vector <int> a, vector <int> b)
  {
    int n = k.size();
    VVI v;
    REP(i, n) v.PB({b[i], a[i], k[i]});
    sort(ALL(v));

    auto check = [&](int mid) -> bool {
      VVI vec = v;
      FOR(i, 1, m+1) {
        int cnt = mid;
        REP(j, n) {
          if(vec[j][1] <= i && i <= vec[j][0]) {
            if(cnt >= vec[j][2]) cnt -= vec[j][2], vec[j][2] = 0;
            else vec[j][2] -= cnt, cnt = 0;
          }
        }
        if(cnt != 0) return false;
      }
      return true;
    };

    int lb=0, ub=5e7+10;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      // cout << lb << " " << mid << " " << ub << endl;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }

    return lb;
  }
};

ARC029 C - 高橋君と国家

競技プログラミング AtCoder

問題ページ
C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder

考えたこと

  • 最小全域木を求めたくなる
  • 最小全域木で使わない辺はいらなさそう
  • 根をcが最も小さい頂点とした根付き木を考えればよさそう
  • 辺を使わないことにして別の頂点を使うみたいなのを繰り返す？
  • 操作一回にO(V+E)かかりそうなので無理だね
  • ある辺より深くにある頂点で辺より頂点の方がcostが小さいなら頂点の方を使いたい
  • dfs一回で何とかならない？
  • 何とかならなさそう
  • 逆にしてある頂点より上にある辺がcostが大きければその辺を消すみたいな
  • 辺を消す操作が難しすぎる
  • 頂点条件を辺条件に置き換えたくなる
  • ある頂点から別の頂点にcostがc[i]の辺を張ったりしたら何とかなってほしい
  • 思いつかない
    -----解説を見た-----
  • 仮想頂点を用意してその頂点から各頂点にcostがc[i]の辺を張る
  • このグラフで最小全域木を求める

最小全域木を求めた && 頂点条件を置き換えようとしたのはいい
dfsで辺を切るようなのはかなりつらそうだし最初に考えることではなさそう
仮想頂点つくるのなんて典型なのに何で思い浮かばなかったのか
頂点条件置き換えで仮想頂点つくるパターンはそこそこありそう

#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 int MOD = 1000000007;

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};

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int s[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

signed main(void)
{
  int n, m;
  cin >> n >> m;
  VI c(n);
  VVI vec(m, VI(3, 0));
  REP(i, n) {
    cin >> c[i];
    vec.PB({c[i], i, n});
  }
  REP(i, m) {
    cin >> vec[i][1] >> vec[i][2] >> vec[i][0];
    vec[i][1]--, vec[i][2]--;
  }
  sort(ALL(vec));

  int ret = 0;
  REP(i, vec.size()) {
    if(!uf.same(vec[i][1], vec[i][2])) {
      uf.unite(vec[i][1], vec[i][2]);
      ret += vec[i][0];
    }
  }

  cout << ret << endl;

  return 0;
}

ARC028 C - 高橋王国の分割統治

競技プログラミング AtCoder

問題ページ
C - 高橋王国の分割統治

考えたこと

  • 明らかに†全方位木DP†をしろという雰囲気をしている
  • d[i] = (頂点iの部分木の頂点数) とする
  • d_par は n-(進む頂点の部分木の頂点数) を渡せばよさそう
  • テンプレに当てはめて書くと通った
#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 int MOD = 1000000007;

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};

VI g[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) {
    int p;
    cin >> p;
    g[p].PB(i+1);
    g[i+1].PB(p);
  }

  // dist[i] = (頂点iの部分木のサイズ)
  VI dist(n);
  function<int(int,int)> dfs1 = [&](int v, int p) -> int {
    if(p != -1 && g[v].size() == 1) return dist[v] = 1;
    for(int &i: g[v]) if(i != p) {
      dist[v] += dfs1(i, v);
    }
    return ++dist[v];
  };

  dfs1(0, -1);

  // ans[i] = (頂点iから最も遠い頂点)
  VI ans(n);
  function<void(int,int,int)> dfs2 = [&](int v, int d_par, int p) {
    // vの子の情報を集める
    vector<PII> d_child;
    // d_child[0], d_child[1]が存在しないのを防ぐ
    d_child.PB({0, -1});
    int sum = 0;
    for(int &i: g[v]) {
      if(i == p) d_child.PB({d_par, i}), sum += d_par;
      else d_child.PB({dist[i], i}), sum += dist[i];
    }
    sort(ALL(d_child), greater<>());
    ans[v] = d_child[0].first;
    for(int &i: g[v]) if(i != p) {
      dfs2(i, sum-dist[i]+1, v);
    }
  };

  dfs2(0, 0, -1);

  REP(i, n) cout << ans[i] << endl;

  return 0;
}

ARC009 C - 高橋君、24歳

競技プログラミング AtCoder

問題ページ
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;
}