题目链接

牛牛的括号式

题目描述

牛牛给出了一个关于未知量 的多项式。这个多项式以字符串的形式表示，它由若干个形如 或 的括号表达式相乘构成。其中， 是一个 0 到 9 之间的数字字符。

牛牛想知道，当这个多项式完全展开后， 的一次项（即 项）的系数是多少？请计算这个系数，由于答案可能很大，请将答案对 10007 取模后输出。

输入:

  • 一个字符串 ，表示给定的多项式。保证字符串 严格由若干个 或 形式的子串拼接而成。

输出:

  • 一个整数，表示多项式展开后 的一次项系数对 10007 取模后的结果。

解题思路

这是一个关于多项式展开求特定项系数的问题。直接模拟整个多项式的展开会非常复杂，因为项的数量会随着乘法次数的增加而指数级增长。

一个更高效的方法是，在每一步乘法中，只追踪我们最终关心的项的系数。为了得到最终的 一次项系数，我们需要观察多项式乘法 的过程。新多项式中的 一次项是由以下两部分相加得到的：

  1. 中的 一次项 乘以 中的 常数项 。
  2. 中的 常数项 乘以 中的 一次项 。

这启发我们，在从左到右处理每个二项式的过程中，我们只需要维护两个值：当前已展开多项式的常数项和** 一次项系数**。

我们可以使用动态规划的思想来解决：

  1. 状态定义:

    • : 当前多项式的 一次项系数。
    • : 当前多项式的常数项。

  2. 初始状态:

    • 在进行任何乘法之前，我们可以认为初始多项式是乘法单位元 1。
    • 因此，初始时 ，。

  3. 状态转移:

    • 当我们用当前多项式（其形式可视为 ... + coeff_x * x + coeff_const）去乘以一个新的二项式 时：
    • 新的常数项 只能由两个常数项相乘得到: 。
    • 新的一次项系数 由上述两种情况相加得到: 。
    • 所有计算都在模 10007 的意义下进行。

  4. 算法流程:

    • 设置模数 。
    • 初始化 。
    • 以 5 个字符为步长遍历输入字符串。在每个 5 字符的块 (xsd) 中，解析出符号 和数字 ，得到常数 。
    • 应用状态转移方程更新 和 ，并时刻取模。
    • 遍历结束后， 的值就是最终答案。由于中间结果可能为负，最后需要 (coeff_x % MOD + MOD) % MOD 来保证结果非负。

代码

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solve() {
    string s;
    cin >> s;

    const int MOD = 10007;

    long long coeff_x = 0;
    long long coeff_const = 1;

    // 字符串由 (xsd) 形式的块拼接而成，每块长度为 5
    for (int i = 0; i < s.length(); i += 5) {
        // s[i+2] 是符号, s[i+3] 是数字
        char sign = s[i + 2];
        int digit = s[i + 3] - '0';
        
        long long a = digit;
        if (sign == '-') {
            a = -a;
        }

        // new_coeff_x = (coeff_x * a) + (coeff_const * 1)
        long long new_coeff_x = (coeff_x * a + coeff_const) % MOD;
        // new_coeff_const = coeff_const * a
        long long new_coeff_const = (coeff_const * a) % MOD;

        coeff_x = new_coeff_x;
        coeff_const = new_coeff_const;
    }

    // 保证结果为非负数
    long long final_result = (coeff_x + MOD) % MOD;
    cout << final_result << endl;
}

int main() {
    solve();
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        final int MOD = 10007;

        long coeffX = 0;
        long coeffConst = 1;

        // 字符串由 (xsd) 形式的块拼接而成，每块长度为 5
        for (int i = 0; i < s.length(); i += 5) {
            // s.charAt(i+2) 是符号, s.charAt(i+3) 是数字
            char sign = s.charAt(i + 2);
            int digit = s.charAt(i + 3) - '0';
            
            long a = digit;
            if (sign == '-') {
                a = -a;
            }

            // newCoeffX = (coeffX * a) + (coeffConst * 1)
            long newCoeffX = (coeffX * a + coeffConst) % MOD;
            // newCoeffConst = coeffConst * a
            long newCoeffConst = (coeffConst * a) % MOD;

            coeffX = newCoeffX;
            coeffConst = newCoeffConst;
        }

        // 保证结果为非负数
        long finalResult = (coeffX + MOD) % MOD;
        System.out.println(finalResult);
    }
}

def solve():
    s = input()
    
    MOD = 10007
    
    coeff_x = 0
    coeff_const = 1
    
    # 字符串由 (xsd) 形式的块拼接而成，每块长度为 5
    for i in range(0, len(s), 5):
        # s[i+2] 是符号, s[i+3] 是数字
        sign = s[i + 2]
        digit = int(s[i + 3])
        
        a = digit
        if sign == '-':
            a = -a
            
        # new_coeff_x = (coeff_x * a) + (coeff_const * 1)
        new_coeff_x = (coeff_x * a + coeff_const) % MOD
        # new_coeff_const = coeff_const * a
        new_coeff_const = (coeff_const * a) % MOD
        
        coeff_x = new_coeff_x
        coeff_const = new_coeff_const
        
    # 保证结果为非负数
    final_result = (coeff_x + MOD) % MOD
    print(final_result)

solve()

算法及复杂度

  • 算法：动态规划
  • 时间复杂度: ，其中 是输入字符串的长度。我们只需要对字符串进行一次线性扫描。
  • 空间复杂度: ，用于存储输入的字符串。