P6103 [EER2] 自然溢出问题

题目背景

题目描述

给定一个整数 ( n )，要求计算有多少个长度为 ( n ) 的字符串满足特定规则，这些字符串被定义为"程序片段"。

具体规则如下：

• 单个分号 ; 是一个"语句"。
• 空串是一个"程序片段"。
• 如果字符串 ( A ) 是"程序片段"，( B ) 是"语句"，则 ( AB ) 是"程序片段"。
• 如果字符串 ( A ) 是"程序片段"，则 {A} 是"语句块"。
• 如果字符串 ( A ) 是"语句块"，则 ( A ) 是"语句"，[]A 和 []()A 是"函数"。
• 如果字符串 ( A ) 是"函数"，则 (A) 是"函数"，A 和 A() 是"值"。
• 如果字符串 ( A ) 是"值"，则 (A) 是"值"，A; 是"语句"。

注意：上述规则中，( A ) 是 ( B ) 并不代表 ( B ) 一定是 ( A )。

输入格式

一行，包含一个整数 ( n )。

输出格式

一行，输出结果对 ( 2^{64} ) 取模后的值。

输入输出样例 #1

输入 #1

4

输出 #1

9

输入输出样例 #2

输入 #2

7

输出 #2

140

数据范围

对于 100% 的数据，( 0 \leq n \leq 10^4 )。

---

C++ 实现

以下是基于动态规划的解决方案：

#include <iostream>
#include <vector>
using namespace std;

const unsigned long long MOD = 18446744073709551616ULL;

unsigned long long fast_read() {
    unsigned long long x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

int main() {
    unsigned int n = fast_read();
    vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(5, 0));
    
    dp[0][1] = 1; // 空字符串是程序片段
    if (n >= 1) dp[1][0] = dp[1][1] = 1; // 单个分号是语句
    
    for (unsigned 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 (unsigned int j = 0; j < i; ++j) {
            dp[i][1] += dp[j][1] * dp[i - j][0]; // 程序片段递归组合
        }
    }
    
    cout << dp[n][1] % MOD;
    return 0;
}

---

解释

代码通过动态规划方法解决问题，定义了五个状态分别表示不同的字符串类型。每个状态根据前一状态进行更新，最终得到满足条件的字符串总数。