結果

問題 No.2174 3 O'clock Easy
ユーザー Nachia
提出日時 2022-12-26 22:14:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 2,944 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-11-21 08:48:12
合計ジャッジ時間 1,167 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math


def regularizedFrac(a) :
    if a[0] == 0 and a[1] == 0 :
        return [0, 1]
    g = math.gcd(abs(a[0]), abs(a[1]))
    if a[0] < 0 and a[1] < 0 :
        g = -g
    return [a[0] // g, a[1] // g]

def negFrac(a) :
    return [-a[0], a[1]]

def addFrac(a, b) :
    return regularizedFrac([a[0] * b[1] + a[1] * b[0], a[1] * b[1]])

def mulFrac(a, b) :
    return regularizedFrac([a[0] * b[0], a[1] * b[1]])

def divFrac(a, b) :
    return regularizedFrac([a[0] * b[1], a[1] * b[0]])

def powFrac(a, t) :
    return regularizedFrac([a[0] ** t, a[1] ** t])

def evalPolynomial(po, x) :
    a = [1, 1]
    res = [0, 1]
    for c in po :
        res = addFrac(res, mulFrac(a, c))
        a = mulFrac(a, x)
    return res

factorialFrac = [[1, 1]]
for j in range(1, 35) :
    factorialFrac.append(mulFrac(factorialFrac[-1], [j, 1]))

def combFrac(n, r) :
    return divFrac(factorialFrac[n], mulFrac(factorialFrac[n-r], factorialFrac[r]))

bernoulliFrac = [[1, 1]]
for n in range(1, 30) :
    tmp = [0, 1]
    for k in range(n) :
        tmp = addFrac(tmp, mulFrac(bernoulliFrac[k], combFrac(n+1, k)))
    bernoulliFrac.append(mulFrac(tmp, [1, -(n+1)]))

integralCoeff = [[[0,1],[1,1]]]
for k in range(1, 30) :
    tmp = [[0, 1]]
    for j in range(1, k+2) :
        tmp.append(mulFrac([1, k+1], mulFrac(combFrac(k+1, k+1-j), bernoulliFrac[k+1-j])))
    integralCoeff.append(tmp)

def addFracPolynomials(a, b) :
    res = [[0,1] for j in range(max(len(a), len(b)))]
    for j in range(len(a)) :
        res[j] = addFrac(res[j], a[j])
    for j in range(len(b)) :
        res[j] = addFrac(res[j], b[j])
    return res

def mulFracPolynomials(a, b) :
    if len(a) == 0 or len(b) == 0 :
        return []
    res = [[0,1] for j in range(len(a) + len(b) - 1)]
    for i in range(len(a)) :
        for j in range(len(b)) :
            res[i+j] = addFrac(res[i+j], mulFrac(a[i], b[j]))
    return res

def powFracPolynomial(a, i) :
    if i == 0 :
        return [[1,1]]
    b = powFracPolynomial(mulFracPolynomials(a, a), i//2)
    if i % 2 == 1 :
        b = mulFracPolynomials(a, b)
    return b

def timesScholarPolynomials(a, t) :
    return [mulFrac(c, t) for c in a]

def talorShift(a, t) :
    res = [[0,1] for j in a]
    for k in range(len(a)) :
        for j in range(k+1) :
            res[j] = addFrac(res[j], mulFrac(combFrac(k,j), mulFrac(a[k], powFrac(t, k-j))))
    return res

def integerIntegral(f) :
    res = []
    for k in range(len(f)) :
        res = addFracPolynomials(res, timesScholarPolynomials(integralCoeff[k], f[k]))
    return res

k1 = [[1,1],[3,1]]
k2 = powFracPolynomial([[2,1],[3,1]], 2)
k3 = powFracPolynomial([[3,1],[3,1]], 3)
ksum = addFracPolynomials(k1, addFracPolynomials(k2, k3))
kintegral = integerIntegral(ksum)

n = int(input())
ans = evalPolynomial(kintegral, [n//3,1])[0]
k = n // 3
if n >= k * 3 + 1 :
    ans += (k * 3 + 1) ** 1
if n >= k * 3 + 2 :
    ans += (k * 3 + 2) ** 2
print(ans)
0