3249 - sumimp3

Cerința

Se citește un număr natural n. Calculați și afișați câte din submulțimile mulțimii {1, 2, ..., n} sunt formate dintr-un număr impar de elemente. Datorită faptului că există foarte multe submulțimi, rezultatul trebuie calculat modulo 9001.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul de submulțimi formate din număr impar de elemente, modulo 9001.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000.000

Exemplu:

Intrare

4

Ieșire

8

Explicație

Submulțimile mulțimii {1, 2, ..., n} care sunt formate dintr-un număr impar de elemente sunt {1}, {1,2,3}, {1,2,4}, {1,3,4}, {2}, {2,3,4}, {3}, {4}.

Rezolvare

MOD = 9001  

def count_odd_subsets(n):
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    dp[0][0] = 1 
    dp[i][0] = 0 

    for i in range(1, n + 1):
        for j in range(i + 1):
            if j == 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD

    odd_subsets = 0
    for j in range(n + 1):
        if j % 2 == 1:
            odd_subsets += dp[n][j]

    return odd_subsets % MOD

def main():
    n = int(input())
    odd_subsets_count = count_odd_subsets(n)
    print(odd_subsets_count)

if __name__ == "__main__":
    main()