Codeforces 474D Flowers（DP)
2024-10-06 22:37:30
[题目链接](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
#include
#include
#include
using namespace std;
typedef pair P;
typedef map M;
typedef vector V;
typedef queue Q;
typedef long long ll;
const int maxn=100000+5;
const ll mo = 1000000000 + 7;
ll dp[maxn];
ll sum[maxn];
int main()
{
int n, a, b, k, i, j, t;
cin >> t >> k;
for (i = 1; i
最新文章
- Linux服务器安全配置
- 关于Django 错误 doesn't declare an explicit app_label and isn't in an application in INSTALLED_APPS
- Discuz门户首页关键词和描述显示“首页”的解决方法
- The main concepts
- mysql中binary相加的问题
- JS实现页面回到顶部效果
- 如何去掉word的背影图片？
- Jquery 自定义事件实现发布/订阅
- 3-Dom
- 【WeX5学习】 后端服务之访问数据库表
- 免费开源ERP Odoo实施指南 连载一：Odoo概述
- [转]一个普通IT人的十年回顾－－－金旭亮
- Booth乘法
- 牛客寒假算法基础集训营3处女座和小姐姐（三） （数位dp）
- [转]PhpStorm中如何使用Xdebug工具，入门级操作方法（亲测有效）
- nativefier(一行代码将任意网页转化为桌面应用)
- ubuntu14.04终端分屏terminator的安装使用与配置
- win10 更新之后，无法开启wifi，“组或资源的状态不是执行请求操作的正确状态”
- 将cmd中命令输出保存为TXT文本文件
- numpy 学习笔记