結果
| 問題 |
No.265 数学のテスト
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:44 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 10,426 bytes |
| コンパイル時間 | 892 ms |
| コンパイル使用メモリ | 76,504 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:18:34 |
| 合計ジャッジ時間 | 2,075 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <cctype> // Use <cctype> for C++ standard library functions like isdigit
// Using standard namespace for convenience
using namespace std;
// Global variable for maximum degree d specified in input.
// The polynomial vector will have size D_MAX + 1, storing coefficients for x^0 to x^D_MAX.
int D_MAX;
// Type alias for Polynomial using vector of long long coefficients.
// Index i corresponds to the coefficient of x^i.
// We use long long to accommodate potentially large coefficients.
using Polynomial = vector<long long>;
// Creates a polynomial representing a constant c.
// P(x) = c * x^0
// Returns a vector representing this polynomial truncated to degree D_MAX.
Polynomial make_const(long long c) {
// Initialize polynomial vector of size D_MAX + 1 with all zeros.
Polynomial p(D_MAX + 1, 0);
// Set the coefficient for x^0 (constant term) if D_MAX >= 0.
if (0 <= D_MAX) {
p[0] = c;
}
return p;
}
// Creates a polynomial representing the variable x.
// P(x) = 1 * x^1
// Returns a vector representing this polynomial truncated to degree D_MAX.
Polynomial make_x() {
// Initialize polynomial vector of size D_MAX + 1 with all zeros.
Polynomial p(D_MAX + 1, 0);
// Set the coefficient for x^1 if D_MAX >= 1.
if (1 <= D_MAX) {
p[1] = 1;
}
// If D_MAX is 0, the polynomial x is represented as [0] effectively, since we only care about coefficient A_0.
return p;
}
// Adds two polynomials p1 and p2.
// Returns the resulting polynomial truncated to degree D_MAX.
// Result coefficient A_i = p1[i] + p2[i]
Polynomial add(const Polynomial& p1, const Polynomial& p2) {
// Initialize result polynomial vector of size D_MAX + 1 with zeros.
Polynomial result(D_MAX + 1, 0);
// Perform element-wise addition for coefficients up to degree D_MAX.
for (int i = 0; i <= D_MAX; ++i) {
result[i] = p1[i] + p2[i];
}
return result;
}
// Multiplies two polynomials p1 and p2.
// Returns the resulting polynomial truncated to degree D_MAX.
// Result coefficient C_k = sum(p1[i] * p2[j]) for all i+j=k.
// Only terms with degree i+j <= D_MAX are considered.
Polynomial multiply(const Polynomial& p1, const Polynomial& p2) {
// Initialize result polynomial vector of size D_MAX + 1 with zeros.
Polynomial result(D_MAX + 1, 0);
// Iterate through coefficients of p1
for (int i = 0; i <= D_MAX; ++i) {
// Optimization: If coefficient p1[i] is 0, terms p1[i]*p2[j]*x^(i+j) are all 0. Skip inner loop.
if (p1[i] == 0) continue;
// Iterate through coefficients of p2
for (int j = 0; j <= D_MAX; ++j) {
// Check if the resulting term's degree (i+j) is within the limit D_MAX.
if (i + j <= D_MAX) {
// Add the product p1[i] * p2[j] to the coefficient of x^(i+j).
// Potential overflow check could be added here if coefficients could exceed long long max,
// but analysis suggests long long is sufficient for given constraints.
result[i + j] += p1[i] * p2[j];
}
// Terms with resulting degree > D_MAX are implicitly ignored.
}
}
return result;
}
// Computes the derivative of polynomial p.
// Returns the resulting polynomial truncated to degree D_MAX.
// If P(x) = sum(A_i * x^i), then P'(x) = sum(A_i * i * x^(i-1)).
// The new coefficient A'_j for x^j is derived from the original coefficient A_{j+1} of x^{j+1}.
// A'_j = A_{j+1} * (j+1).
Polynomial differentiate(const Polynomial& p) {
// Initialize result polynomial vector of size D_MAX + 1 with zeros.
Polynomial result(D_MAX + 1, 0);
// Iterate from i=1 because the constant term A_0 disappears upon differentiation.
for (int i = 1; i <= D_MAX; ++i) {
// The term A_i * x^i becomes A_i * i * x^(i-1).
// This contributes to the coefficient of x^(i-1) in the derivative polynomial.
// Cast i to long long during multiplication to prevent potential integer overflow if p[i] is large.
result[i - 1] = p[i] * (long long)i;
}
// The coefficient for x^D_MAX in the result will be 0, because it would come from differentiating a term with x^(D_MAX+1),
// which is beyond the maximum degree D_MAX stored in p. This is handled by initialization to zeros.
return result;
}
// Global parser state: current position index in the expression string S.
// Used by recursive parser functions to track progress through the string.
int pos;
// Global expression string. Storing globally avoids passing copies in recursion.
string S;
// Forward declarations for recursive descent parser functions.
// These functions implement the grammar rules and operator precedence.
Polynomial parse_expression_global(); // Handles '+' operations
Polynomial parse_term_global(); // Handles '*' operations
Polynomial parse_factor_global(); // Handles base units: constants, 'x', 'd{...}'
// Parses an expression according to the grammar: Expression ::= Term { '+' Term }
// Expressions are sums of terms. Addition has lower precedence.
Polynomial parse_expression_global() {
// An expression starts with a term.
Polynomial result = parse_term_global();
// Check for subsequent terms connected by '+'.
while (pos < S.length() && S[pos] == '+') {
pos++; // Consume the '+' operator
Polynomial next_term = parse_term_global(); // Parse the term following '+'
result = add(result, next_term); // Add the parsed term to the running total
}
// Return the final polynomial representing the evaluated expression.
return result;
}
// Parses a term according to the grammar: Term ::= Factor { '*' Factor }
// Terms are products of factors. Multiplication has higher precedence than addition.
Polynomial parse_term_global() {
// A term starts with a factor.
Polynomial result = parse_factor_global();
// Check for subsequent factors connected by '*'.
while (pos < S.length() && S[pos] == '*') {
pos++; // Consume the '*' operator
Polynomial next_factor = parse_factor_global(); // Parse the factor following '*'
result = multiply(result, next_factor); // Multiply the running result by the parsed factor
}
// Return the final polynomial representing the evaluated term.
return result;
}
// Parses a factor according to the grammar: Factor ::= Constant | VariableX | 'd{' Expression '}'
// Factors are the basic building blocks of the expression.
Polynomial parse_factor_global() {
// Basic check for boundary conditions or end of relevant context (like finding '}')
if (pos >= S.length() || S[pos] == '}') {
// If '}' is encountered, it signifies the end of a 'd{...}' block, which should be handled by the calling context.
// Returning zero polynomial can signal this, or simply rely on caller to check pos.
// If end of string is reached unexpectedly, it implies malformed input.
// Under problem constraints (valid input), this case might signal expected end (like closing brace).
return Polynomial(D_MAX + 1, 0); // Return zero polynomial as a safe default/fallback.
}
// Identify the type of factor based on the character at the current position 'pos'.
if (isdigit(S[pos])) {
// Factor is a constant (guaranteed to be single digit 1-9 by problem statement).
long long val = S[pos] - '0'; // Convert character digit to integer value.
pos++; // Advance parser position past the digit.
return make_const(val); // Return the polynomial representation of the constant.
} else if (S[pos] == 'x') {
// Factor is the variable 'x'.
pos++; // Advance parser position past 'x'.
return make_x(); // Return the polynomial representation of 'x'.
} else if (S[pos] == 'd') {
// Factor is a differentiation operation 'd{...}'.
pos++; // Consume 'd'.
// Check for opening brace '{' which must follow 'd'.
if (pos >= S.length() || S[pos] != '{') {
// Error condition: Input format violation (should not happen with valid input).
return Polynomial(D_MAX+1, 0);
}
pos++; // Consume '{'.
// Recursively call parse_expression_global() to parse the expression inside the braces.
// This recursive call will consume characters until it hits the matching closing brace '}'.
Polynomial expr_poly = parse_expression_global();
// After the recursive call returns, 'pos' should be pointing at the matching '}'.
// Check for the closing brace '}' to confirm correct structure.
if (pos >= S.length() || S[pos] != '}') {
// Error condition: Input format violation (mismatched braces or structure error).
return Polynomial(D_MAX+1, 0);
}
pos++; // Consume '}'.
// Compute and return the derivative of the parsed inner expression polynomial.
return differentiate(expr_poly);
} else {
// If the character at S[pos] doesn't match any expected factor type, it indicates an error
// or an unexpected situation (e.g., encountering '}' incorrectly).
// Return zero polynomial for robustness. Valid inputs shouldn't reach here improperly.
return Polynomial(D_MAX + 1, 0);
}
}
int main() {
// Optimize C++ standard input/output streams for performance.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Length of the expression string S (provided but not directly used in parsing logic).
cin >> N >> D_MAX >> S; // Read N, maximum degree d, and the expression string S.
pos = 0; // Initialize the global parser position to the start of the string S.
// Call the top-level parser function parse_expression_global() to evaluate the entire expression.
Polynomial final_poly = parse_expression_global();
// Output the resulting polynomial coefficients A_0, A_1, ..., A_D_MAX.
for (int i = 0; i <= D_MAX; ++i) {
cout << final_poly[i] << (i == D_MAX ? "" : " "); // Print each coefficient followed by a space, except for the last one.
}
cout << endl; // Print a newline character at the end of the output.
return 0; // Indicate successful program execution.
}