[text] rook

Viewer

  1. from copy import deepcopy
  2. n, m = map(int, input().split())
  3. mod = 1000_000_033
  4. dp = [[0] * m for _ in range(n)]
  5. dp[0][0] = 1
  6. for j in range(1, m):
  7.     dp[0][j] = 1 if j == 1 else (dp[0][j - 1] * 2) % mod
  8. for i in range(1, n):
  9.     dp[i][0] = 1 if i == 1 else (dp[i - 1][0] * 2) % mod
  10. pref = deepcopy(dp)
  11. for i in range(1, n):
  12.     s1 = 0
  13.     for j in range(1, m):
  14.         s1 += dp[i][j - 1] % mod
  15.         dp[i][j] = (s1 % mod + pref[i - 1][j] % mod) % mod
  16.         pref[i][j] = (pref[i - 1][j] % mod + dp[i][j] % mod) % mod
  17. print(dp[n - 1][m - 1] % mod)

Editor

You can edit this paste and save as new:


File Description
  • rook
  • Paste Code
  • 04 Feb-2023
  • 565 Bytes
You can Share it: