Pascal Bit Sum

2 secs 1024 MB

問題文

X_{l,r}=1 \quad (l=0\lor r=0),\quad X_{l-1,r} \oplus X_{l,r-1} \quad otherwise

と $X_{l,r}$ を ( $l \geq 0, r \geq 0$ ) で定義します。

ただし、 $\oplus$ は xor である、つまり

0 \oplus 0 = 0,\quad 0 \oplus 1 = 1,\quad 1 \oplus 0 = 1,\quad 1 \oplus 1 = 0

です。

長さ $N$ の配列 $A$ が与えられるので

\sum_{i=0}^{k} A_i X_{i,k-i}

を $0 \leq k < N$ について mod $10^9 + 7$ で求めてください。

入力は以下の形式で標準入力から与えられます。

$N$
$A_1$ $A_2$ $\dots$ $A_N$

答えを $N$ 行で出力してください。 $i$ 行目に $k=i-1$ のときの計算結果を出力してください。

4
2 1 3 4

2
877914575 602436426

877914575
480350994

登録なしで提出できます。

Go (1.21)