Official

D - Flip Cards Editorial by en_translator


Consider determining the choice of cards from the first card in order. Whether to flip the \(i\)-th card is only dependent on whether to flip the \((i-1)\)-th card. Now, consider the following DP (Dynamic Programming).

\({\rm DP}[i][{\rm flag}] =\) the number of ways to determine whether to flip the first \(i\) cards such that the \(i\)-th card (flag ? is : is not) flipped.

This DP has \(O(N)\) states and costs \(O(1)\) time for a transition, so the problem can be solved in a total of \(O(N)\) time.

Sample code (Python)

MOD=998244353

N=int(input())
data=[tuple(map(int,input().split())) for _ in range(N)]
dp=[[0,0] for _ in range(N)]
dp[0]=[1,1]
for i in range(1,N):
  # 配るDP
  for pre in range(2):
    for nxt in range(2):
      if data[i-1][pre]!=data[i][nxt]:
        dp[i][nxt]+=dp[i-1][pre]
  dp[i][0]%=MOD
  dp[i][1]%=MOD

print((dp[N-1][0]+dp[N-1][1])%MOD)

posted:
last update: