洛谷 U138345 太极棋

洛谷 U138345 太极棋

洛谷传送门

题目背景

某日午后，SeawaySeawa**y一觉醒来，发现自己穿越到了《天龙八部》的世界，并成为了一名棋士......在反穿越失败后，SeawaySeawa**y接受了这个事实，并尝试着成为天下第一棋士......

题目描述

经过多年的浸淫与历练，SeawaySeawa**y渐渐领悟了棋道的真谛，并自创一派：“太极棋派”。在太极棋派的棋社中，棋盘的长为NN，对应万象众生，但宽只为22，对应乾（天）和坤（地）；棋子只有黑白两种颜色，对应太极两仪。在对弈过程中，两方各要算出：在棋盘上摆满黑白两种棋子后，棋盘上的颜色块个数正好为KK的方案数。哪一方算得又快又准即获胜。SeawaySeawa**y作为此派的创教掌门，在太极棋领域纵横天下三十六载，无人能敌。现在他要把掌门之位传给你——只要你能够证明，你能下好每一盘太极棋。

输入格式

从文件taichi.intaich**i.i**n中读入数据。

一行两个整数N,KN,K。

输出格式

输出到文件taichi.outtaich**i.out中。

仅一行一个整数，表示当前棋局的方案数。由于答案可能很大，你只需要输出你的答案对998244353998244353取模的结果。

---

命题说明：

没啥可说明的。

---

题解：

思路：计数——思考计数类DP。

既然已经是DP了，考虑设置状态。

直觉设置：(dp[i][j])表示前i列共有j个连通块的方案数。但是这样没办法转移。

思考转移：如何能够转移呢？显然，当前面的状态已经算出来的时候，当前状态统计答案肯定要和当前这一列的黑白染色情况有关的。

也就是说，和当前状态有关。思考状压。

可以用两位二进制表示当前列的黑白染色情况，分别转移。

两位？......大可不必状压吧。我们发现，这个状态一共只有4种情况，上黑下白，上白下黑，全黑，全白。

那直接多开一维存1~4就行，没必要状压。

转移方程见代码。非常好想。

初值、答案也见代码：

#include<cstdio>
#define int long long
using namespace std;
const int mod=998244353;
int n,k;
int dp[1010][2010][5];
//dp[i][j][opt]表示前i列，j个连通块，第i列型号为opt的方案数。
signed main()
{
	scanf("%lld%lld",&n,&k);
	dp[1][1][3]=dp[1][1][4]=dp[1][2][2]=dp[1][2][1]=1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			dp[i][j][3]=(dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j-1][4])%mod;
			dp[i][j][4]=(dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j-1][3]+dp[i-1][j][4])%mod;
			if(j>1)
			{
				dp[i][j][1]=(dp[i-1][j-1][4]+dp[i-1][j][1]+dp[i-1][j-2][2]+dp[i-1][j-1][3])%mod;
				dp[i][j][2]=(dp[i-1][j-2][1]+dp[i-1][j][2]+dp[i-1][j-1][3]+dp[i-1][j-1][4])%mod;
			}
		}
	int ans=(dp[n][k][1]+dp[n][k][2]+dp[n][k][3]+dp[n][k][4])%mod;
	printf("%lld",ans);
	return 0;
}