結果

問題 No.303 割れません
ユーザー qwewe
提出日時 2025-04-24 12:25:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,331 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 53,860 KB
最終ジャッジ日時 2025-04-24 12:25:58
合計ジャッジ時間 11,942 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    L = int(sys.stdin.readline())
    if L == 0:
        print("INF")
        print(0)
        return
    
    if L % 2 == 1:
        # For odd L, the answer is the number of ways to partition L into an odd number of odd parts
        # The minimal cost is L, and the count is the number of compositions into odd parts with odd count
        # The number of such compositions is known to be Fibonacci numbers
        # Specifically, for L=2k+1, the count is Fib(L)
        # But since we need to compute it, we use a DP approach
        max_half = (L + 1) // 2
        dp = [0] * (L + 2)
        dp[0] = 1
        for i in range(1, L + 1):
            for k in range(1, i + 1, 2):
                if i - k >= 0:
                    dp[i] += dp[i - k]
        print(L)
        print(dp[L])
        return
    else:
        # For even L, need to compute even number of odd parts, subtract those where midpoint is a joint
        # Compute the number of compositions of L into even number of odd parts
        # and subtract the square of the number of compositions of L/2 into any number of odd parts
        # Compute using two DPs: even and odd counts
        max_L = L
        even = [0] * (max_L + 1)
        odd = [0] * (max_L + 1)
        even[0] = 1
        odd[0] = 0
        for i in range(1, max_L + 1):
            for k in range(1, i + 1, 2):
                if i - k >= 0:
                    even[i] += odd[i - k]
                    odd[i] += even[i - k]
            even[i] %= 10**18
            odd[i] %= 10**18
        if even[L] == 0:
            print("INF")
            print(0)
            return
        half = L // 2
        # Compute the number of compositions of half into any number of odd parts
        dp_half = [0] * (half + 1)
        dp_half[0] = 1
        for i in range(1, half + 1):
            for k in range(1, i + 1, 2):
                if i - k >= 0:
                    dp_half[i] += dp_half[i - k]
            dp_half[i] %= 10**18
        forbidden = (dp_half[half] ** 2) % 10**18
        total = (even[L] - forbidden) % 10**18
        if total < 0:
            total += 10**18
        if even[L] == 0:
            print("INF")
            print(0)
        else:
            print(L)
            print(total if total != 0 else 0)

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