글 읽기 - 시간 초과 질문입니다.

methe12345 10달 전 0

주어진 식을 f(x) 라고 하면 우리가

출력하고자 싶은 것을 처음부터 나열해보면

이렇게 된다 라고 생각하고 풀었는데 시간초과가 계속 나옵니다..

혹시 더 빠르게 계산 할 수 있는 방법이 있을까 물어봅니다.

import sys
import math

input = sys.stdin.readline
N = int(input())
poly = list(map(int, input().split()))

# 기저 사례
if N == 0:
    print(f'GGG<{poly[0]}>')
    exit(0)

mod = (10**9) + 7
cache = [-1]*(N+1)

# 조합
def comb(n, m):
    up = math.factorial(n)
    down = (math.factorial(n - m)) * (math.factorial(m))
    return (up // down) % mod

# 다항식 계산 arr[i] 는 arr[i]*(x**i)임
# arr = f(x) cal(arr, x) = f(x)
def cal(arr: list, x: int) -> int:
    # print(arr, x)
    if x == 0:
        return arr[0]
    if x == 1:
        return sum(arr) % mod
    ret = 0
    for i in range(len(arr)):
        ret += arr[i]*(x**i)
    return ret % mod

for i in range(N+1):
    cache[i] = cal(poly, i)

ans = [poly[0]]

for i in range(1, N+1):
    m = 0
    for j in range(i):
        m += (cache[j+1] * comb(i-1, j) * ((-1)**(i-j-1)))
    m %= mod
    m = ((m - ans[-1])+mod) % mod
    ans.append(m)

a = ','.join(map(str, ans))
print(f'GGG<{a}>')

methe12345 10달 전 0

https://sagecell.sagemath.org/

다음 사이트에서 아래 소스코드를 입력하시면 뭔가 깨닫는게 있을 것입니다...

이 문제를 푸는 모든 분들 화이팅입니다..특히 파이썬으로 푸는 분들

a1 = var('a1')
a2 = var('a2')
a3 = var('a3')
a4 = var('a4')
a5 = var('a5')
a6 = var('a6')
a0 = var('a0')
x = var('x')
f(x) = a0 + a1*x + a2*(x**2) + a3 * (x**3) + a4 * (x**4) + a5 * (x**5) + a6*(x**6)
g(x) = f(x+1) - f(x)
h(x) = g(x+1) - g(x)
i(x) = h(x+1) - h(x)
j(x) = i(x+1) - i(x)
k(x) = j(x+1) - j(x)
l(x) = k(x+1) - k(x)
print(f(0))
print(expand(g(0)))
print(expand(h(0)))
print(expand(i(0)))
print(expand(j(0)))
print(expand(k(0)))
print(expand(l(0)))
print(f(x))
print(expand(g(x)))
print(expand(h(x)))
print(expand(i(x)))
print(expand(j(x)))
print(expand(k(x)))
print(expand(l(x)))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과 질문입니다.

methe12345 10달 전 0

methe12345 10달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말