g555 - 白色世界(簡易版)

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算將一條長度為 n 的道路上的格子染色，使得不染色、單獨染色，或染色格子之間至少空一個格子的方案數，並將結果模 998244353 輸出。

解題思路

本題可以使用動態規劃來解決。定義 dp[i][0] 表示長度為 i 的道路，最後一個格子不染色的方案數，dp[i][1] 表示長度為 i 的道路，最後一個格子染色的方案數。

狀態轉移方程如下：

• dp[i+1][0] = (dp[i][0] + dp[i][1]) % mod：如果第 i+1 個格子不染色，則前 i 個格子的方案可以是最後一個格子不染色或染色的方案。
• dp[i+1][1] = dp[i][0] % mod：如果第 i+1 個格子染色，則前 i 個格子必須不染色。

最終答案為 dp[n-1][2]，其中 dp[i][2] 表示長度為 i 的道路的染色方案數，且不包含都不染色的情況，即 dp[i][2] = (dp[i][0] + dp[i][1] - 1) % mod。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
long long dp[200005][3],mod=998244353,t,n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	dp[0][0]=dp[0][1]=1;
	for(int i=0;i<=200000;++i){
		dp[i+1][0]=(dp[i+1][0]+dp[i][0]+dp[i][1])%mod;
		dp[i+1][1]=(dp[i+1][1]+dp[i][0])%mod;
		dp[i][0]%=mod;
		dp[i][1]%=mod;
		dp[i][2]=(dp[i][0]+dp[i][1]-1)%mod;
	}
	cin >> t;
	for(int i=0;i<t;++i){
		cin >> n;
		cout << dp[n-1][2] << "\n";
	}
}