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|)$ になる.
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月25日00時39分14秒
Last modified: 2017年05月05日05時42分18秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_hourrank-20
トップページに戻る
Logged in as: unknown user (not login)