No.3243 Multiplication 8 1
タグ : / 解いたユーザー数 61
作問者 :
AngrySadEight
/ テスター :
遭難者
👑 
ygussany
問題文
整数 $N$ が与えられます．各要素が $1, 2, -1, -2$ である長さ $N$ の数列 $A$ であって，次の条件を満たすものの個数を $998244353$ で割った余りを求めてください．
- 数列 $A$ を空でない $1$ 個以上の区間に分割する方法であって，分割された後のすべての区間において区間内の要素の総積が $8$ となるものが存在する．
- より厳密には，正整数 $L$ と $0 = B_1 < B_2 < \dots < B_L = N$ を満たす長さ $L$ の整数列 $B$ であって，次の条件を満たすものが存在する．
- $A_{B_i + 1} \times A_{B_i + 2} \times \dots \times A_{B_{i+1}} = 8 \ (1 \leq i \leq L - 1)$
$T$ 個のテストケースが与えられるので，それぞれに対して答えてください．
制約
- 入力は全て整数
- $1 \leq T \leq 888$
- $1 \leq N \leq 8.88 \times 10^{17}$
入力
入力は以下の形式で標準入力から与えられる．ここで，$\mathrm{case}_i$ は $i$ 番目のテストケースを表す．
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられる．
$N$
出力
$T$ 行出力せよ．$i$ 行目には，$i$ 番目のテストケースに対する答えを出力せよ．
サンプル
サンプル1
入力
8 1 3 4 8 88 888 888888888 888000000000000000
出力
0 4 32 9200 744976062 355614226 995875110 722933621
$1$ 番目のテストケースについて，条件を満たす長さ $1$ の数列 $A$ は存在しないので，答えは $0$ 通りです．
$2$ 番目のテストケースについて，条件を満たす長さ $3$ の数列 $A$ としては，$A = (2, 2, 2), (2, -2, -2), (-2, 2, -2), (-2, -2, 2)$ の $4$ 通りがあります．
$3$ 番目のテストケースについて，条件を満たす長さ $4$ の数列 $A$ の例として $A = (1, 2, -2, -2)$ や $(-2, -2, -2, -1)$ などが挙げられ，全部で $32$ 通りあります．
$4$ 番目のテストケースについて，条件を満たす長さ $8$ の数列 $A$ の例としては $A = (2, 2, -2, 1, -1, -2, 2, -2)$ が挙げられます．この数列を $(2, 2, -2, 1, -1)$ と $(-2, 2, -2)$ に分割することで，分割された後の数列の各要素の積は全て $8$ となるためです．
条件を満たす数列 $A$ の個数を $998244353$ で割った余りを出力することに注意してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。