- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 91 lines of Python from the credited upstream file abc405_e.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4class Combination:5 """Count the total number of combinations.6 nCr % mod.7 nHr % mod = (n + r - 1)Cr % mod.8 9 Args:10 max_value: Max size of list. The default is 500,05011 mod : Modulo. The default is 10 ** 9 + 7.12 13 Landau notation: O(n)14 15 See:16 http:drken1215.hatenablog.com/entry/2018/06/08/21000017 """18 19 def __init__(self, max_value=500050, mod=10**9 + 7):20 self.max_value = max_value21 self.mod = mod22 self.fac = [0 for _ in range(self.max_value)]23 self.finv = [0 for _ in range(self.max_value)]24 self.inv = [0 for _ in range(self.max_value)]25 26 self.fac[0] = 127 self.fac[1] = 128 self.finv[0] = 129 self.finv[1] = 130 self.inv[1] = 131 32 for i in range(2, self.max_value):33 self.fac[i] = self.fac[i - 1] * i % self.mod34 self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod i) % self.mod35 self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod36 37 def count_nCr(self, n, r):38 """Count the total number of combinations.39 nCr % mod.40 nHr % mod = (n + r - 1)Cr % mod.41 42 Args:43 n : Elements. Int of number (greater than 1).44 r : The number of r-th combinations. Int of number45 (greater than 0).46 47 Returns:48 The total number of combinations.49 50 Landau notation: O(1)51 """52 53 if n < r:54 return 055 if n < 0 or r < 0:56 return 057 58 return self.fac[n] * (self.finv[r] * self.finv[n - r] % self.mod) % self.mod59 60 61def main():62 import sys63 64 input = sys.stdin.readline65 66 a, b, c, d = map(int, input().split())67 mod = 99824435368 comb = Combination(max_value=4 * 10**6 + 10, mod=mod)69 ans = 070 71 72 73 74 75 76 77 78 79 80 for b1 in range(b + 1):81 count1 = comb.count_nCr(a + b1 - 1, b1)82 count2 = comb.count_nCr(b - b1 + c + d, c)83 ans += count1 * count284 ans %= mod85 86 print(ans)87 88 89if __name__ == "__main__":90 main()91