fork(1) download
  1. # your code goes here
  2. from functools import lru_cache
  3. import sys
  4. from time import time
  5.  
  6. sys.setrecursionlimit(1000000)
  7.  
  8. mod = 998244353
  9.  
  10. @lru_cache(maxsize=None)
  11. def fs(k, n):
  12. if k <= 0 or n <= 0:
  13. return 0
  14. elif n == 1:
  15. return 2 if k == 1 else 0
  16.  
  17. return (fs(k-1, n-1) + 2*fd(k, n-1) + fs(k, n-1)) % mod
  18.  
  19. @lru_cache(maxsize=None)
  20. def fd(k, n):
  21. if k <= 0 or n <= 0:
  22. return 0
  23. elif n == 1:
  24. return 2 if k == 2 else 0
  25. return (2*fs(k-1, n-1) + fd(k-2, n-1) + fd(k, n-1)) % mod
  26.  
  27. start = time()
  28. n, k = map(int, input().split())
  29. print((fs(k, n) + fd(k, n)) % mod)
  30. end = time()
  31.  
  32. print(f'time: {end-start}')
Success #stdin #stdout 2.16s 284908KB
stdin
1000 2000
stdout
2
time: 2.015707492828369