D - 揺れる街、増える敵 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(600\) 点

ストーリー

「いったい、なんだったんでしょうか…」帰り道、いろはちゃんがぽつぽつと話し始める。 「さっきの化け物、明らかにおかしいです」「あんなの、この世界にいていいものじゃありません」「あれはまるで、バグ…」

彼女の言葉を遮るように、轟音が響き渡った。しかも、今度は何回も。僕たちは顔を見合わせ、走り出した。

問題文

\(T\) 個の街で、それぞれ敵が出現した。

\(i\) 番目の街で出現した敵は、一列に並んだマス状の形をしており、元々のマスの個数は \(1\) 個以上 \(L_i\) 個以下である。 街ではすでに敵のマスのうち \(0\) 個以上を破壊し、敵は破壊されたマスで分割されたいくつかの部分に分かれている。マスの個数が \(L\) の敵は、端から \(i\) 番目のマスを破壊されると、マスの個数がそれぞれ \(i-1\) と \(L-i\) の \(2\) つの敵に分割される(ただし、マスの個数が \(0\) の敵は消滅する)。

しかし、その敵は分割されると強くなってしまうものだった。具体的には、マスの個数が \(p_1, p_2, \dots, p_n\) である \(n\) 個の部分に分割されたとき、敵の強さは全体で \(p_1\times p_2\times\dots\times p_n\) になってしまう。

現在、\(i\) 番目の街では敵の強さが \(2^{A_i}\) 以上になってしまったという。敵の元々のマスの個数としてありうるものが何通りあるかを、\(T\) 個の街に現れた敵それぞれについて求めよ。

制約

  • 入力はすべて整数
  • \(1≦T≦300\)
  • \(1≦L_i≦10^9,\ 0≦A_i≦10^9\)

入力

入力は以下の形式で与えられる。

\(T\)
\(L_1\) \(A_1\)
\(L_2\) \(A_2\)
:
\(L_T\) \(A_T\)

出力

\(T\) 行出力し、\(i\ (1≦i≦T)\) 行目には \(i\) 番目の街に出現した敵に対する答えを出力せよ。

入力例

4
9 3
13 4
11 6
11235813 213455

出力例

3
5
0
10702177

\(1\) 番目の街に出現した敵の元々のマスの個数は \(7, 8, 9\) の \(3\) 通りがあり得る。

それぞれ、敵が次のように破壊されたの場合に条件を満たす(oはマスが破壊されていないことを、xは破壊されていることを表す)。

  • 敵の元々のマスの個数が \(7\) : ooxoooo (敵の強さは \(8\))
  • 敵の元々のマスの個数が \(8\) : ooxooxoo (敵の強さは \(8\))
  • 敵の元々のマスの個数が \(9\) : oooxoxooo (敵の強さは \(9\))

\(2\) 番目の街に出現した敵の元々のマスの個数は \(9, 10, 11, 12, 13\) の \(5\) 通りがあり得る。

それぞれ、次のような破壊のされ方の場合に条件を満たす。

  • 敵の元々のマスの個数が \(9\) : ooooxoooo (敵の強さは \(16\))
  • 敵の元々のマスの個数が \(10\) : ooxooxoooo (敵の強さは \(16\))
  • 敵の元々のマスの個数が \(11\) : oooxooooxoo (敵の強さは \(24\))
  • 敵の元々のマスの個数が \(12\) : oooooooooxoo (敵の強さは \(18\))
  • 敵の元々のマスの個数が \(13\) : ooooxoooooooo (敵の強さは \(32\))

\(3\) 番目の街に出現した敵の元々のマスの個数は \(0\) 通りがあり得る。

解説

解説