题解 P6103 【[EER2]直接自然溢出啥事没有】
xht
2020-02-18 14:16:57
考虑递推，设 $f_i$ 表示长度为 $i$ 的「程序片段」，有 $f_0 = 1$。
注意到，「程序片段」只能是「程序片段」$+$「语句」，若设 $c_i$ 表示长度为 $i$ 的「语句」个数，则有 $f_{i} = \sum_{j=0}^{i-1} f_jc_{i-j}$，则可以 $\mathcal O(n^2)$ 递推。
考虑什么东西能当「语句」。
首先，`;` 为一个「语句」，因此有 $f_i \leftarrow f_{i-1}$。
除此之外，「语句」都必须由另外一个「程序片段」生成。
我们枚举这个「程序片段」的长度 $j$，设其为 `A`，则 `A` 的个数为 $f_j$。
它会生成 `{A}`「语句块」和 `{A}`「语句」，此时出现了「语句」，则有 $f_i \leftarrow f_{i-j-2} \times f_{j}$。
如果此时我们还想生成「语句」，那么只能走这样一条路：「语句」$\to$「函数」$\to$「值」$\to$「语句」 。
然后就无法再生成更多的「语句」了。
「语句」$\to$「函数」的过程实际上就是长度 $+2$ 或 $+4$。
「值」$\to$「语句」的过程实际上就是长度 $+1$。
我们只需要考虑「函数」$\to$「值」的过程，这也是最复杂的一个过程。
对于一个长度为 $l$ 的「函数」`A`，它会变成：
- 一个长度为 $l$ 的值 `A`；
- 两个长度为 $l+2$ 的值 `(A),A()`；
- 三个长度为 $l+4$ 的值 `((A)),(A()),(A)()`；
- 四个长度为 $l+6$ 的值 `(((A))),((A())),((A)()),((A))()`；
- $\cdots$
- $n$ 个长度为 $l+(n-1)\times 2$ 的值。
考虑到「语句」$\to$「函数」的过程长度 $+2$ 或 $+4$，「值」$\to$「语句」的过程长度 $+1$。
将这些信息整合起来可以得到 $f_i \leftarrow f_j \sum_{k=1}^{i-j-4} [k \bmod 2 = 1]k \cdot f_{i-j-4}$。
于是我们可以写出下面这个 $\mathcal O(n^3)$ 的程序：
```cpp
const int N = 1e4 + 7;
int n;
ul f[N];
int main() {
rd(n), f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = f[i-1];
for (int j = 0; i - j - 2 >= 0; j++) {
ul o = f[i-j-2];
for (int k = 1; i - j - k - 4 >= 0; k += 2)
o += f[i-j-k-4] * k;
f[i] += o * f[j];
}
}
print(f[n]);
return 0;
}
```
然而，数据范围要求我们在 $\mathcal O(n^2)$ 的时间复杂度内解决。
考虑优化，注意到 $\sum_{k=1}^{i-j-4} [k \bmod 2 = 1]k \cdot f_{i-j-4}$ 这玩意儿可以前缀和优化 $\mathcal O(1)$ 得到，于是时间复杂度降为 $\mathcal O(n^2)$。
至于对 $2^{64}$ 取模，题目名已经告诉我们怎么做了。
```cpp
const int N = 1e4 + 7;
int n;
ul f[N], g[N];
int main() {
rd(n), f[0] = g[1] = 1;
for (int i = 1; i <= n; i++) {
f[i] = f[i-1];
for (int j = 0; i - j - 2 >= 0; j++)
f[i] += f[i-j-2] * f[j];
for (int j = 0; i - j - 4 >= 0; j++)
f[i] += g[i-j-4] * f[j];
for (int j = 1; i + 1 - j >= 0; j += 2)
g[i+1] += f[i+1-j] * j;
}
print(f[n]);
return 0;
}
```