Codeforces 474D Flowers(DP)
分类:
IT文章
•
2022-05-20 19:58:40
[题目链接](http://codeforces.com/problemset/problem/474/D)
非常简单的一道dp题,通过O(n)的预处理来使查询变为O(1)。
主要的坑在于取模后的dp数组的前缀和再相减可能得到负数,导致无法得到某一区间和的取模。
解决方法:(a-b)%mo==(a%mo+mo-b%mo)%mo,由于该等式的存在,可以使用取模后的前缀和做运算得到某一区间和的取模。
代码:
```C++
#include
#include
#include
#include
#include
#include
#include