問題概要
Alice と Bob が複数回に渡ってじゃんけんをする.各ラウンドで,相手に勝利したプレイヤーが 1 ポイントを得る.
今,各ラウンドで Bob が出す手は分かっている.Bob の戦略の情報は配列 で与えられ, は 番目のラウンドで Bob が出す手を表す(0 -> グー, 1 -> チョキ,2 -> パー).
Alice が合計 ポイントを獲得するための手の出しかたは何通りあるか? 答えを として, を計算せよ.
解法
を と書きます.
まず, でなければ絶対に達成できないので, のときの答えは 0 となります.
次に, ポイントを取得可能な場合について考えます. ポイントを取得する場合というのを詳しく述べると,
- 回の勝ち
- 回の勝ち以外(あいこ or 負け)
となります.勝つラウンドが決まっているとすると,残りの ラウンドで出せる手の組合せは,勝つ手以外の 2 通りを 回選択することになるので, 通りです.また,勝つラウンドの選び方は, 個のものから 個を選択する組合せの数なので,二項係数 となります.勝つラウンドには手の選択肢が無いので,勝つラウンドが決まっていれば手の出し方は 1 通りに定まります.従って答えは (勝つラウンドの選び方)×(勝たないラウンドの手の出し方) を表す です.
二項係数をパスカルの三角形を DP する方法で求めるとすると,この部分が最も時間のかかる処理となり,全体のオーダーは 時間となります.
二項係数と反復二乗法をライブラリにしていれば,かなり少ない実装量で解くことができます.
コード
#define SZ( v ) ( (int)( v ).size() ) // a^x を mod で求める // 反復二乗法 long long mod_pow( long long a, long long x, long long mod ); // パスカルの三角形による nCr の計算 // 剰余系版 // 前処理 O( N^2 ), クエリ O( 1 ) class PascalTriangle; // PascalTriangle( N ) // ()( n, r ) constexpr int MOD = 1000000007; PascalTriangle nCr( 2000, MOD ); class RockPaperScissorsMagicEasy { public: int count( vector <int> card, int score ) { const int N = SZ( card ); return score <= N ? ( mod_pow( 2, N - score, MOD ) * nCr( N, score ) ) % MOD : 0; } };