[Python] Cumulative sum ABC179D

ABC179D As a simple solution,

dp[i]:=Number of operation rows until reaching mass i

A dynamic programming method that tries all movements for each location i can be considered, but the time complexity is $ O (N ^ 2) $. The update formula is as follows.

dp[i] = \sum_{v\in S} dp[i-v] \\

In such cases, it is standard to use cumulative sum to speed up DP. First, paying attention to the fact that the set S consists of K intervals, the part of $ \ sum_ {v \ in S} dp [iv] $ is the sum of the "sums within the intervals" for the K intervals. It turns out to be a thing. Recall that, in general, the sum of the intervals [l, r) of array a can be represented by s [r]-s [l], where s is the cumulative sum of array a. Therefore, if the cumulative sum of the array dp is sumdp, the update expression can be transformed as follows.

dp[i] = \sum_{k=1}^K (sumdp[i-l_k+1]-sumdp[i-r_k]) \\

The amount of calculation is $ O (NK) $.

(Reference) Be able to write cumulative sums without thinking!

Sample code


MOD = 998244353
N, K = map(int, input().split()) #N is the number of squares, K is the number of sections(K is 10 or less)
sec = [tuple(map(int, input().split())) for _ in range(K)]

dp = [0] * (N+1)
dp[1] = 1

sumdp = [0] * (N+1)
# i-l=1(Current trout)When it becomes, dp[i]Increase by 1
sumdp[1] = 1

# i=Sumdp in order from 2 to N[i]To update
for i in range(2, N+1):
    #Dp by cumulative sum sumdp in each interval[i]To update
    for l, r in sec:
        li = max(i - l, 0)
        ri = max(i - r - 1, 0)

        dp[i] += sumdp[li] - sumdp[ri]
        dp[i] %= MOD

    sumdp[i] = sumdp[i-1] + dp[i]

print(dp[N])

Recommended Posts

[Python] Cumulative sum ABC186D
[Python] Cumulative sum ABC179D
Learn cumulative sum in Python
[Python] ABC175D
Cumulative sum commentary
[Python] DP ABC184D
[Python] UnionFind ABC177D
Solve ABC168D in Python
Solve ABC167-D in Python
[Python] Interval scheduling ABC103D
[Python] Binary search ABC155D
Solve ABC159-D in Python
Implement sum in Python
[Python] Dynamic programming ABC015D
[Python] BFS (breadth-first search) ABC168D
Cumulative sum and potato method
ABC161D Lunlun Number with python3
[Python] DFS (Depth-first Search) ABC157D
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Python
[Python] How to derive nCk (ABC156-D)
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
(Python) ABC162-D Consideration log and solution
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
PRML Chapter 8 Product Sum Algorithm Python Implementation
Project Euler # 16 "Sum of Powers" in Python
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers