表裏に数字が書かれたカードがN枚あり、隣接するカードの数字が異なるように裏返したりしなかったりしたときの組合せを998244353で割ったあまりを求める。
制約
- 1≤N≤2×105
- 1≤Ai,Bi≤109
解説
問題文の通り、すべてのカードの裏表の組合せを列挙する場合は
2Nだけあり、今回の制約では2secで計算することができない。
今回の場合、各カードの裏表を出力する必要はないため、
i番目のカードを表とした時と裏にした時の組合せの数だけがわかれば良い。
また、
i番目のカードの値を決める時には両隣の数値と異なる必要があるが、既に値が決まっている
i−1番目のカードだけ見れば、
i番目のカードの表裏を決めることができる。
したがって、各カードを表にした時と裏にした時のそこまでで決まっているカードの組合せの数を足すことで、組合せの数をDPによって計算することができる。
DP[i][0]を
i番目を表にした時のそこまでの組合せの数、
DP[i][1]を裏にした時の組合せの数として、
N番目のカードを表、裏にした時の組合せの和のあまりを出力することで、
O(N)答えを求めることができる。