2018.09.21codeforces1051D.Bicolorings（线性dp）

传送门
sb线性DP。
$f[i][j][0/1/2/3]$表示前i列j个连通块且第i列状态为00/01/10/11时的方案总数。
这个显然可以轻松转移。
举例&＃xff1a;
$f[i][j][0]\&＃61;(f[i-1][j][0]\&＃43;f[i-1][j][1]\&＃43;f[i-1][j][2]\&＃43;f[i-1][j-1][3])$
其它几个同理。
代码&＃xff1a;

#include
#define mod 998244353
#define ll long long
#define N 1005
using namespace std;
inline long long read(){long long ans&＃61;0;char ch&＃61;getchar();while(!isdigit(ch))ch&＃61;getchar();while(isdigit(ch))ans&＃61;(ans<<3)&＃43;(ans<<1)&＃43;(ch^48),ch&＃61;getchar();return ans;
}
int n,k;
ll f[N][N*2][4];
int main(){cin>>n>>k;f[1][1][0]&＃61;1;f[1][1][3]&＃61;1;f[1][2][1]&＃61;1;f[1][2][2]&＃61;1;for(int i&＃61;2;i<&＃61;n;&＃43;&＃43;i){int up&＃61;min(i*2,k);for(int j&＃61;1;j<&＃61;up;&＃43;&＃43;j){f[i][j][0]&＃61;(f[i-1][j][0]&＃43;f[i-1][j][1]&＃43;f[i-1][j][2]&＃43;f[i-1][j-1][3])%mod;f[i][j][1]&＃61;(f[i-1][j-1][0]&＃43;f[i-1][j][1]&＃43;f[i-1][j-1][3])%mod;if(j>&＃61;2)(f[i][j][1]&＃43;&＃61;f[i-1][j-2][2])%&＃61;mod;f[i][j][2]&＃61;(f[i-1][j-1][0]&＃43;f[i-1][j][2]&＃43;f[i-1][j-1][3])%mod;if(j>&＃61;2)(f[i][j][2]&＃43;&＃61;f[i-1][j-2][1])%&＃61;mod;f[i][j][3]&＃61;(f[i-1][j-1][0]&＃43;f[i-1][j][1]&＃43;f[i-1][j][2]&＃43;f[i-1][j][3])%mod;}}cout<<(f[n][k][0]&＃43;f[n][k][1]&＃43;f[n][k][2]&＃43;f[n][k][3])%mod;return 0;
}