2017年05月05日05時42分18秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

HackerRank HourRank 20 2問目 - Counting Perfect Subsequences

Source

HourRank 20 2問目
problem statement（コンテストページ）

問題概要

アルファベット小文字の a, b, c, d のみからなる文字列 $S$ が与えられる．
$S$ の空でない部分列の中で，含まれる a の数と b の数が等しい，かつ，含まれる c の数と d の数が等しいものは何個あるかを $\bmod 1000000007\ (10^9+7)$ で求める問題．

解法

文字列 $S$ に含まれる a, b, c, d の数 $A,B,C,D$ をそれぞれ求める．
後は，a, b を同じ数だけ選ぶ方法
\[ \sum_{i} {A \choose i} {B \choose i} \]と c, d を同じ数だけ選ぶ方法
\[ \sum_{i} {C \choose i} {D \choose i} \]をそれぞれ求めて掛け算すれば答えになる．
二項係数は予め階乗を求めておけば高速に計算可能．
もしくは，
\[ \sum_i {A \choose i} {B \choose i} = \sum_i {A \choose i} {B \choose B-i} = {A+B \choose B} \]を用いても良い．
何れにしても各テストケースごとに時間計算量は $O(|S|)$ になる．

cLay（version 20170505-2）のコード

C++に変換後のコードはこちら

int Q, N;
char S[500010];
{
  int hist[4];
  combination_mint comb;
  mint res, ab, cd;

  comb.init(500010);

  rd(Q);
  while(Q--){
    rd(S@N);

    hist[0..3] = 0;
    hist[S[0..N-1]-'a']++;

    ab = cd = 0;
    ab += comb.C(hist[0],(0..N)) * comb.C(hist[1],(0..));
    cd += comb.C(hist[2],(0..N)) * comb.C(hist[3],(0..));
    
    res = ab * cd - 1;
    wt(res);
  }
}

Current time: 2024年04月20日19時59分36秒
Last modified: 2017年05月05日05時42分18秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_hourrank-20
トップページに戻る

Logged in as: unknown user (not login)

ログイン：