Danciu: Pagină nouă: = 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...

2024-06-04T08:40:15Z

Pagină nouă: = 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...

New page

= 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>

3249 - sumimp3 - Revision history