题解 P6103 【[EER2]直接自然溢出啥事没有】
Warriors_Cat
·
·
题解
题解 P6103 【[EER2]直接自然溢出啥事没有】
最近一直在做树论和数论的题目，\text{DP} 题倒是做得比较少，导致比赛的时候这道题没想出来。借这道题我再回顾一下我的 \text{DP}，顺便码一篇题解给大家。
Solution:
这道题看似复杂，实际上我们一句一句来分析就很简单。
首先，我们定义状态如下：
$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]
那么 $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$:
```cpp
#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