結果

問題 No.265 数学のテスト
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:13:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,254 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 397,604 KB
最終ジャッジ日時 2025-06-12 21:15:19
合計ジャッジ時間 7,300 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    d = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()

    def parse_expression(s, i, max_degree):
        terms = []
        terms.append(parse_term(s, i, max_degree))
        while i[0] < len(s) and s[i[0]] == '+':
            i[0] += 1
            terms.append(parse_term(s, i, max_degree))
        result = [0] * (max_degree + 1)
        for term in terms:
            for degree in range(max_degree + 1):
                result[degree] += term[degree]
        return result

    def parse_term(s, i, max_degree):
        factors = []
        factors.append(parse_factor(s, i, max_degree))
        while i[0] < len(s) and s[i[0]] == '*':
            i[0] += 1
            factors.append(parse_factor(s, i, max_degree))
        result = [0] * (max_degree + 1)
        result[0] = 1
        for factor in factors:
            new_result = [0] * (max_degree + 1)
            for deg1 in range(max_degree + 1):
                if result[deg1] == 0:
                    continue
                for deg2 in range(max_degree + 1):
                    if factor[deg2] == 0:
                        continue
                    total_deg = deg1 + deg2
                    if total_deg > max_degree:
                        continue
                    new_result[total_deg] += result[deg1] * factor[deg2]
            result = new_result
        return result

    def parse_factor(s, i, max_degree):
        if s[i[0]] == 'd':
            i[0] += 1
            if i[0] >= len(s) or s[i[0]] != '{':
                raise ValueError("Expected '{' after 'd'")
            i[0] += 1
            start = i[0]
            depth = 1
            while i[0] < len(s) and depth > 0:
                if s[i[0]] == '{':
                    depth += 1
                elif s[i[0]] == '}':
                    depth -= 1
                if depth == 0:
                    break
                i[0] += 1
            if depth != 0:
                raise ValueError("Unmatched '{' in d{} expression")
            end = i[0]
            sub_expr = s[start:end]
            sub_i = [0]
            sub_poly = parse_expression(sub_expr, sub_i, max_degree)
            derived = differentiate(sub_poly, max_degree)
            i[0] += 1
            return derived
        elif s[i[0]].isdigit():
            num = int(s[i[0]])
            i[0] += 1
            poly = [0] * (max_degree + 1)
            poly[0] = num
            return poly
        elif s[i[0]] == 'x':
            i[0] += 1
            poly = [0] * (max_degree + 1)
            if max_degree >= 1:
                poly[1] = 1
            return poly
        else:
            raise ValueError(f"Unexpected character: {s[i[0]]}")

    def differentiate(poly, max_degree):
        new_poly = [0] * (max_degree + 1)
        for degree in range(1, len(poly)):
            if degree - 1 <= max_degree:
                new_poly[degree - 1] += degree * poly[degree]
        return new_poly

    i = [0]
    try:
        final_poly = parse_expression(S, i, d)
        print(' '.join(map(str, final_poly)))
    except Exception as e:
        print(e)
        sys.exit(1)

if __name__ == '__main__':
    main()
0