提出 #8229129

---

ソースコード 拡げる

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・どうせ、十分先では適切な周期で3次関数
・小さい方を調べると、12個おきに見ると3次関数であることが分かる
"""

MOD = 10**9 + 7

L = int(readline())

def naive_solution(L):
    cnt = 0
    for a in range(1,L):
        for b in range(a+1,L):
            for c in range(b+1,L):
                if b-a != 1 and c-b != 1:
                    continue
                if a+b <= c:
                    break
                if a+b+c > L:
                    break
                cnt += 1
    return cnt

A = [naive_solution(L) for L in range(100)]

if L < 100:
    answer = A[L]
else:
    x = 99
    while (L-x)%12:
        x -= 1
    x -= 36
    n = (L-x)//12
    a,b,c,d = A[x:x+37:12]
    """
    f(0)=a,f(1)=b,f(2)=c,f(3)=d,f(n)=answer 
    """
    answer = a*(n-1)*(n-2)*(n-3)//(-6)
    answer += b*(n-0)*(n-2)*(n-3)//2
    answer += c*(n-0)*(n-1)*(n-3)//(-2)
    answer += d*(n-0)*(n-1)*(n-2)//6
answer %= MOD
print(answer)

提出情報

ジャッジ結果