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: