cho.sh

Fygon

아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

프레데릭은 대회에 나갈 때마다 가장 좋아하는 언어 Fygon으로 문제를 푼다. Fygon 인터프리터가 느린 탓에 점근적으로 최적인 알고리즘을 짜도 시간 초과를 받는 일이 잦고, 그래서 상수 배 최적화로 시간 제한을 맞춘다. 어떤 최적화가 값어치를 하는지 판단하려면 프로그램이 수행하는 연산 횟수를 정확히 알아야 한다.

Fygon에는 문장이 두 종류뿐이다. 첫 번째는 lag으로, 다른 거의 모든 문장을 대신한다. 두 번째는 for 반복문이다.

for <variable> in range(<limit>):
    <body>

반복 변수는 0부터 시작해 <limit>보다 작은 정수를 차례로 훑는다. 변수는 a부터 z까지의 소문자이고, <limit>은 이미 정의된 변수이거나 양의 정수 상수다. 반복문의 <body>는 공백 네 칸으로 들여쓰고 문장이 하나 이상 들어 있다.

프로그램은 입력을 변수 n으로 받는다. n은 특별한 의미가 있어 반복 변수로 쓸 수 없다.

Fygon 프로그램이 주어지면 이 프로그램이 실행하는 lag 연산의 횟수를 n에 대한 식으로 구하라.

입력

입력은 Fygon 프로그램 전체다. 서로 다른 두 반복문은 같은 반복 변수를 쓰지 않는다. range 안에 나오는 변수는 n이거나 바깥쪽 반복문이 선언한 변수다. 프로그램의 문장은 20개 이하이고 그중 반복문은 6개 이하다. 정수 상수는 모두 1 이상 9 이하다. 중첩 한 단계마다 공백 네 칸을 들여쓰며, 각 줄은 lag이거나 for <variable> in range(<limit>): 형태다.

출력

lag 연산의 횟수를 f(n)f(n)이라 하자. ff는 nn에 대한 유리계수 다항식이다. 이를 전개한 f(n)=cdnd+cd−1nd−1+⋯+c0f(n) = c_d n^d + c_{d-1} n^{d-1} + \dots + c_0 꼴로 보고, 아래 규칙에 따라 한 줄에 공백 없이 출력한다.

계수가 0이 아닌 항만 지수가 큰 것부터 차례로 적는다. 지수가 kk이고 계수가 cc인 항은 ∣c∣|c|를 적은 다음 *n을 kk번 이어 붙인다. ∣c∣|c|는 분모가 양수인 기약분수 p/q로 적되, 분모가 1이면 p만 적는다. 계수가 1이어도 생략하지 않는다. 첫 항은 계수가 음수일 때만 앞에 -를 붙이고, 두 번째 항부터는 계수가 양수면 +를, 음수면 -를 붙인다. ff가 항상 0이면 0 하나만 출력한다.

예를 들어 f(n)=112n2−12n+5f(n) = \frac{11}{2}n^2 - \frac{1}{2}n + 5이면 11/2*n*n-1/2*n+5를 출력하고, lag이 한 번도 실행되지 않는 프로그램이면 0을 출력한다.