Editing 3249 - sumimp3


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

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul de submulțimi formate din număr impar de elemente, modulo <code>9001</code>.

= Restricții și precizări =

* <code>1 ≤  n ≤ 2.000.000.000</code>

= Exemplu: =
Intrare
 4
Ieșire
 8

=== Explicație ===
Submulțimile mulțimii <code>{1, 2, ..., n}</code> care sunt formate dintr-un număr impar de elemente sunt <code>{1}</code>, <code>{1,2,3}</code>, <code>{1,2,4}</code>, <code>{1,3,4}</code>, <code>{2}</code>, <code>{2,3,4}</code>, <code>{3}</code>, <code>{4}</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
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()

</syntaxhighlight>