- 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
- 76 lines of Python from the credited upstream file abc156_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 Args:9 max_value: Max size of list. The default is 500,05010 mod : Modulo. The default is 10 ** 9 + 7.11 Landau notation: O(n)12 See:13 http:drken1215.hatenablog.com/entry/2018/06/08/21000014 """15 16 def __init__(self, max_value=500050, mod=10 ** 9 + 7):17 self.max_value = max_value18 self.mod = mod19 self.fac = [0 for _ in range(self.max_value)]20 self.finv = [0 for _ in range(self.max_value)]21 self.inv = [0 for _ in range(self.max_value)]22 23 self.fac[0] = 124 self.fac[1] = 125 self.finv[0] = 126 self.finv[1] = 127 self.inv[1] = 128 29 for i in range(2, self.max_value):30 self.fac[i] = self.fac[i - 1] * i % self.mod31 self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod i) % self.mod32 self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod33 34 def count_nCr(self, n, r):35 """Count the total number of combinations.36 nCr % mod.37 nHr % mod = (n + r - 1)Cr % mod.38 Args:39 n : Elements. Int of number (greater than 1).40 r : The number of r-th combinations. Int of number41 (greater than 0).42 Returns:43 The total number of combinations.44 Landau notation: O(1)45 """46 47 if n < r:48 return 049 if n < 0 or r < 0:50 return 051 52 return self.fac[n] * (self.finv[r] * self.finv[n - r] % self.mod) % self.mod53 54 55def main():56 import sys57 58 input = sys.stdin.readline59 60 n, k = map(int, input().split())61 62 k = min(k, n - 1)63 mod = 10 ** 9 + 764 c = Combination(n + 100)65 ans = 066 67 for zero_count in range(k + 1):68 ans += c.count_nCr(n, zero_count) * c.count_nCr(n - 1, zero_count)69 ans %= mod70 71 print(ans)72 73 74if __name__ == "__main__":75 main()76