当前位置:网站首页>2327. 知道秘密的人数(递推)
2327. 知道秘密的人数(递推)
2022-07-06 04:11:00 【Harris-H】
2327. 知道秘密的人数(递推)
一维dp就可以qwq。令 f i f_i fi表示第 i i i天新知道秘密的人数。
第 i i i天可以由 ( i − f o r g e t , i − d e l a y ] (i-forget,i-delay] (i−forget,i−delay] 递推。
显然可以预处理前缀和,做到 O ( n ) O(n) O(n)
最后的答案就是: ∑ i = n − f o r g e t + 1 n f i \sum\limits_{i=n-forget+1}^n f_i i=n−forget+1∑nfi
class Solution {
const int MOD = 1000000007;
public:
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<long long> f(n + 1), g(n + 1);
f[1] = g[1] = 1;
for (int i = 2; i <= n; i++) {
int L = max(0, i - forget);
int R = max(0, i - delay);
f[i] = (g[R] - g[L] + MOD) % MOD;
g[i] = (g[i - 1] + f[i]) % MOD;
}
return (g[n] - g[max(0, n - forget)] + MOD) % MOD;
}
};
边栏推荐
- The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
- Script lifecycle
- 10個 Istio 流量管理 最常用的例子,你知道幾個?
- In Net 6 CS more concise method
- During pycharm debugging, the view is read only and pause the process to use the command line appear on the console input
- 1291_ Add timestamp function in xshell log
- Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
- How does technology have the ability to solve problems perfectly
- MySQL about self growth
- Mlapi series - 04 - network variables and network serialization [network synchronization]
猜你喜欢
MySQL about self growth
记一次excel XXE漏洞
Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
MySQL learning record 13 database connection pool, pooling technology, DBCP, c3p0
[Key shake elimination] development of key shake elimination module based on FPGA
综合能力测评系统
题解:《单词覆盖还原》、《最长连号》、《小玉买文具》、《小玉家的电费》
Stable Huawei micro certification, stable Huawei cloud database service practice
What is the difference between gateway address and IP address in tcp/ip protocol?
图应用详解
随机推荐
【FPGA教程案例11】基于vivado核的除法器设计与实现
查询mysql数据库中各表记录数大小
P3033 [usaco11nov]cow steelchase g (similar to minimum path coverage)
ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
MySQL learning record 13 database connection pool, pooling technology, DBCP, c3p0
判断当天是当月的第几周
[FPGA tutorial case 11] design and implementation of divider based on vivado core
Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
Global and Chinese markets for fire resistant conveyor belts 2022-2028: Research Report on technology, participants, trends, market size and share
80% of the diseases are caused by bad living habits. There are eight common bad habits, which are both physical and mental
DM8 backup set deletion
Class A, B, C networks and subnet masks in IPv4
QML和QWidget混合开发(初探)
Stc8h development (XII): I2C drive AT24C08, at24c32 series EEPROM storage
In depth MySQL transactions, stored procedures and triggers
Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
HotSpot VM
How can programmers resist the "three poisons" of "greed, anger and ignorance"?
MySQL transaction isolation level