青木くんとすぬけくんの作戦のみに注目したとき、\(i\) 回目のじゃんけんの結果としてありうるのは次の \(4\) 通りです。

1. 高橋くんがパーを出すと、高橋くんだけが勝つ（\(2\) 人ともグーを出す）
2. 高橋くんがグーを出すと、高橋くんだけが勝つ（\(2\) 人ともチョキを出す）
3. 高橋くんがチョキを出すと、高橋くんだけが勝つ（\(2\) 人ともパーを出す）
4. 高橋くんが何をを出しても、高橋くんだけが勝つことはない（\(2\) 人が別々の手を出す）

\(k\) 回のじゃんけんそれぞれがこの \(4\) 通りのうちどれであるかを表す列 \((v_1,\dots,v_t)\) を 相手の作戦 と呼ぶことにします。

相手の作戦の確率分布を\(O(k4^k)\) で求める

まず、相手の作戦が \(4^k\) 通りのうちどれになるかを表す確率分布を求める方法を考えます。

自明な方針として、ありうる \(nm\) 通りすべてを確かめる方法がありますが、これでは \(O(k9^k)\) かかってしまいます。 そこで、高速ゼータ変換のような dp を使った畳み込みをします。

方針

\(v_i=1,2,3\) として、\(A_{v_1,\dots,v_k}\) を青木くんが以下の条件を満たす確率とします。

• \(v_i=1\) のとき、\(i\) 回目にグーを出す。
• \(v_i=2\) のとき、\(i\) 回目にチョキを出す。
• \(v_i=3\) のとき、\(i\) 回目にパーを出す。

\(v_i=1,2,3,4\) として、\(A'_{v_1,\dots,v_k}\) を青木くんが以下の条件を満たす確率とします。

• \(v_i=1\) のとき、\(i\) 回目にグーを出す。
• \(v_i=2\) のとき、\(i\) 回目にチョキを出す。
• \(v_i=3\) のとき、\(i\) 回目にパーを出す。
• \(v_i=4\) のときは何を出しても良い。

\(\{A_{v_1,\dots,v_k}\}_{v_1,\dots,v_n=1,2,3,4}\) から \(\{A'_{v_1,\dots,v_k}\}_{v_1,\dots,v_n=1,2,3,4}\) を求める処理を \(f\) とおきます。

すぬけくんについても同様に \(B_{v_1,\dots,v_k},B'_{v_1,\dots,v_k}\) を定義します。 すると、 \(C'_{v_1,\dots,v_k}:=A'_{v_1,\dots,v_k}B'_{v_1,\dots,v_k}\) は次を満たす確率になります。

• \(v_i=1\) のとき、\(i\) 回目に \(2\) 人ともグーを出す。
• \(v_i=2\) のとき、\(i\) 回目に \(2\) 人ともチョキを出す
• \(v_i=3\) のとき、\(i\) 回目に \(2\) 人ともパーを出す
• \(v_i=4\) のときは何を出しても良い。

よって、\(C_{v_1,\dots,v_k}\) を \(\{C'_{v_1,\dots,v_k}\}_{v_i=1,2,3,4} = f(\{C_{v_1,\dots,v_k}\}_{v_i=1,2,3,4})\) を満たす数列とすると、\(C_{v_1,\dots,v_k}\) が求める確率分布となります。

実装

\(\{A_{v_1,\dots,v_k}\}_{v_1,\dots,v_n=1,2,3,4}\) は入力から直接求められます。

\(f\) は、高速ゼータ変換と同様に、各 \(i\) について、 \(v_i\neq 4\) であるそれぞれの項 \(A_{v_1,\dots,v_k}\) を \(A_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\) に足していくことで計算できます。 つまり、\(A^0_{v_1,\dots,v_k}:=A_{v_1,\dots,v_k}\) として、各 \(i\) について、\(A^{i+1}_{v_1,\dots,v_k}\) を次のように求め、\(A'_{v_1,\dots,v_k}:=A^k_{v_1,\dots,v_k}\) とすれば良いです(ここで、上付き文字は累乗ではなく、添字です)。

• \(A^{i+1}_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}\)
• \(A^{i+1}_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}\)
• \(A^{i+1}_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}\)
• \(A^{i+1}_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+A^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+A^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+A^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)

なお、 \(A^j_{v_1,\dots,v_k}\) は以下を満たす確率です。

• \(i<j\) となる \(i\) について
  • \(v_i=1\) のとき、\(i\) 回目にグーを出す。
  • \(v_i=2\) のとき、\(i\) 回目にチョキを出す。
  • \(v_i=3\) のとき、\(i\) 回目にパーを出す。
  • \(v_i=4\) のときは何を出しても良い。
• \(i\ge j\) となる \(i\) について、
  • \(v_i=1\) のとき、\(i\) 回目にグーを出す。
  • \(v_i=2\) のとき、\(i\) 回目にチョキを出す。
  • \(v_i=3\) のとき、\(i\) 回目にパーを出す。
  • （\(v_i=4\) のときは何を出してもだめ。）

\(f\) の逆関数も同様です。 つまり、各 \(i\) について、 \(v_i\neq 4\) であるそれぞれの項 \(A'_{v_1,\dots,v_k}\) を \(A'_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\) から引いていくことで計算できます。

相手の作戦の確率分布から答えを\(O(k4^k)\) で求める

次に、求めた確率分布から、高橋くんの作戦それぞれについて、高橋くんが喜ばない確率を求めます。これも先ほどと似たような、添字の項ごとの変換を使って求めることができます。

\(v_i=1,2,3,4\) として、\(D_{v_1,\dots,v_k}\) を以下の条件を満たす確率とします。

• \(v_i=1\) のとき、\(i\) 回目に「 \(2\) 人ともグーを出す」以外。
• \(v_i=2\) のとき、\(i\) 回目に「 \(2\) 人ともチョキを出す」以外。
• \(v_i=3\) のとき、\(i\) 回目に「 \(2\) 人ともパーを出す」以外。
• \(v_i=4\) のときは何を出しても良い。

\(C_{v_1,\dots,v_k}\) から \(D_{v_1,\dots,v_k}\) を求めるためには、 \(C_{v_1,\dots,v_k}^0:=C_{v_1,\dots,v_k}\) として、各 \(i\) について、 \(C^{i+1}_{v_1,\dots,v_k}\) を次のように求め、\(D_{v_1,\dots,v_k}:=C^k_{v_1,\dots,v_k}\) とすれば良いです。

• \(C^{i+1}_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)
• \(C^{i+1}_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)
• \(C^{i+1}_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)
• \(C^{i+1}_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)

これで、高橋くんが喜ばない確率 \(D_{v_1,\dots,v_k}\) が求まったため、\(1-D_{v_1,\dots,v_k}\) が答えです。

C++による実装例