[cf] EDU 188 D.MEX Sequences dp计数问题

前言

传送门 :

思路

对于这个题,我们会发现,有且仅有两个串,也就是两种状态

1. 0 , 0 , 1 , 1 , 2 , 2 0,0,1,1,2,2 0,0,1,1,2,2 这种显然是很平凡的一种
2. 0 , 0 , 1 , 1 , 3 , 3 , 1 , 1 , 3 , 3 0,0,1,1,3,3,1,1,3,3 0,0,1,1,3,3,1,1,3,3 显然如果你选取了 x + 2 x+2 x+2的时候,那么不可能在继续选下去了,为了保证序列中的 X i − M E X < = 1 X_i-MEXn; ll dp[n+4][2] = {0}; dp[0][0] = 1; for(int i=1;i>x;x++; //防止0的情况 导致下标负数 dp[x][0] += dp[x][0]+dp[x-1][0]; dp[x][1] += dp[x][1]; dp[x+2][1] += dp[x+2][1]; if(x>1) dp[x][1] += dp[x-2][0]; dp[x][0]%=mod; dp[x][1]%=mod; dp[x+2][1]%=mod; } ll ans = 0; for(int i=1;i