自动搬运

查看原文

来自洛谷，原作者为

	Warriors_Cat 欢迎来到这方净土，这里曾有一位普通人建造着自己的乌托邦。

搬运于2025-08-24 22:17:27，当前版本为作者最后更新于2020-02-18 20:58:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P6103 【[EER2]直接自然溢出啥事没有】

最近一直在做树论和数论的题目，$\text{DP}$ 题倒是做得比较少，导致比赛的时候这道题没想出来。借这道题我再回顾一下我的 $\text{DP}$，顺便码一篇题解给大家。

$Solution$:

这道题看似复杂，实际上我们一句一句来分析就很简单。

首先，我们定义状态如下：

$dp[i][0]$：表示长度为 $i$ 的字符串中 “语句” 的个数。

$dp[i][1]$：表示长度为 $i$ 的字符串中 “程序片段” 的个数。

$dp[i][2]$：表示长度为 $i$ 的字符串中 “语句块” 的个数。

$dp[i][3]$：表示长度为 $i$ 的字符串中 “函数” 的个数。

$dp[i][4]$：表示长度为 $i$ 的字符串中 “值” 的个数。

然后我们一句一句来分析：

$(i.)$ 单个分号 ; 是一个“语句”。

那么 $dp\left[1\right]\left[0\right]=1$。

$(ii.)$ 空串 是一个“程序片段”。

那么 $dp\left[0\right]\left[1\right]=1$。

$(iii.)$ 如果字符串 A 是“程序片段”，字符串 B 是“语句”，则 AB 是“程序片段”。

那么 $dp\left[1\right]\left[1\right]=1$，$dp\left[i\right]\left[1\right]=\sum_{j=0}^{i-1}dp\left[j\right]\left[1\right]\times dp\left[i-j\right]\left[0\right]$。

$(iv.)$ 如果字符串 A 是“程序片段”，则 {A} 是“语句块”。

那么 $dp\left[i\right]\left[2\right]=dp\left[i-2\right]\left[1\right]$。

$(v.)$ 如果字符串 A 是“语句块”，则 A 是“语句”，[]A 和 []()A 都是“函数”。

那么 $dp\left[i\right]\left[0\right]=dp[i][2]$，$dp\left[i\right]\left[3\right]=dp\left[i-2\right]\left[2\right]+dp\left[i-4\right]\left[2\right]$。

$(vi.)$ 如果字符串 A 是“函数”，则 (A) 是“函数”，A 和 A() 都是“值”。

那么 $dp\left[i\right]\left[3\right]+=dp\left[i-2\right]\left[3\right]$，$dp\left[i\right][4]=dp\left[i\right]\left[3\right]+dp\left[i-2\right]\left[3\right]$

$(vii.)$ 如果字符串 A 是“值”，则 (A) 是“值”，A; 是“语句”。

那么 $dp\left[i\right][4]+=dp\left[i-2\right]\left[4\right]$，$dp\left[i\right]\left[0\right]+=dp\left[i-1\right]\left[4\right]$。

燃鹅这里有个问题，就是 $dp\left[i\right]\left[4\right]$ 加上 $dp\left[i-2\right]\left[4\right]$ 后可能会出现重复，所以这一 $part$ 要去掉。

总和以上分析，代码就呼之欲出啦0^_^0。

至于对 $2^{64}$ 取模，根据题目可得直接溢出即可。

$Code$:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int unsigned long long
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}//快读板板
inline void write(int x){
	if(x < 0) putchar('-'), x = -x;
	if(x / 10 == 0){
		putchar(x % 10 + 48);
		return;
	}
	write(x / 10);
	putchar(x % 10 + 48);
}//快输板板
int n, dp[100010][5];
// 0: 语句
// 1: 程序片段
// 2: 语句块
// 3: 函数
// 4: 值 
signed main(){
	n = read();
	dp[0][1] = dp[1][0] = dp[1][1] = 1;
	for(int i = 2; i <= n; ++i){
		dp[i][3] = dp[i - 2][2] + dp[i - 2][3];
		if(i >= 4) dp[i][3] += dp[i - 4][2];
		dp[i][2] = dp[i - 2][1];
		dp[i][0] = dp[i][2] + dp[i - 1][4];
		dp[i][4] = dp[i][3] + dp[i - 2][4];//注意这里
		for(int j = 0; j < i; ++j) dp[i][1] += dp[j][1] * dp[i - j][0];//根据上述情况模拟
	}
	write(dp[n][1]);//完结撒花-v-
	return 0;
}

End