https://www.acmicpc.net/problem/24548
문제요약
- T, G, P, F의 개수가 3의 배수인 구간의 경우의 수
접근법
- 전에 K의 배수 이런 문제를 누적합으로 풀었었음
- 누적합 mod 결과를 누적합에 저장하고 이전 위치에서 차가 0이 되는 값을 찾는 접근법
- 7의 배수가 되는 것을 구하는데, 특정 위치까지 합이 6(mod 7) 이었으면, 이전 위치까지에서 합이 6(mod 7)인 것들을 빼면 7의 배수가 된다 이런 식
- [T][G][P][F]의 개수만큼 누적시켜나감
- 특정 시점의 (T, G, P, F)의 개수가 (1, 0, 2, 0)이라면, 이전 위치에서 누적합이 (1, 0, 2, 0)였던 개수를 구하면 됨
- 개수를 구하고 누적합을 갱신해줌
newbieski