- Define precisely what one DP state represents.
- Establish the base cases before transitions are evaluated.
- Process states in dependency order and combine only already-known values.
Code notes
- 97 lines of Python from the credited upstream file abc358_e.py.
- The implementation visibly relies on sequence storage, ordered lookup, cached states.
- No explicit loop blocks detected.
Complexity
Multiply the number of reachable states by the work performed for each transition, then include the stored state table in memory usage.
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 k = int(input())67 c = list(map(int, input().split()))68 dp = [0] * (k + 1)69 dp[0] = 170 size = 10**371 mod = 99824435372 ans = 073 74 combination = Combination(max_value=10**3 + 10, mod=mod)75 76 for ci in c:77 ndp = [0] * (k + 1)78 79 for j in range(size + 1):80 for add in range(ci + 1):81 nj = j + add82 83 if nj > k:84 break85 86 ndp[nj] += dp[j] * combination.count_nCr(nj, add)87 ndp[nj] %= mod88 89 dp = ndp90 91 ans = sum(dp[1:]) % mod92 print(ans)93 94 95if __name__ == "__main__":96 main()97