当前位置:网站首页>2327. Number of people who know secrets (recursive)
2327. Number of people who know secrets (recursive)
2022-07-06 04:15:00 【Harris-H】
2327. Number of people who know the secret ( Recurrence )
A one-dimensional dp Can qwq. Make f i f_i fi It means the first one i i i Tianxin knows the number of Secrets .
The first i i i Days can be controlled by ( i − f o r g e t , i − d e l a y ] (i-forget,i-delay] (i−forget,i−delay] Recurrence .
Obviously, prefixes and , Achieve O ( n ) O(n) O(n)
The final answer is : ∑ 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;
}
};
边栏推荐
- Codeforces Round #770 (Div. 2) B. Fortune Telling
- 51nod 1130 n factorial length V2 (Stirling approximation)
- PTA tiantisai l1-078 teacher Ji's return (15 points) detailed explanation
- P3500 [POI2010]TES-Intelligence Test(二分&离线)
- Le compte racine de la base de données MySQL ne peut pas se connecter à distance à la solution
- [tomato assistant installation]
- 综合能力测评系统
- Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
- 判断当天是当月的第几周
- 2/11 matrix fast power +dp+ bisection
猜你喜欢
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
Redis (replicate dictionary server) cache
自动化测试的好处
【leetcode】1189. Maximum number of "balloons"
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
Thread sleep, thread sleep application scenarios
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
综合能力测评系统
VNCTF2022 WriteUp
Le compte racine de la base de données MySQL ne peut pas se connecter à distance à la solution
随机推荐
VPP performance test
Benefits of automated testing
User datagram protocol UDP
asp. Core is compatible with both JWT authentication and cookies authentication
2/13 review Backpack + monotonic queue variant
Unity中几个重要类
HotSpot VM
脚本生命周期
Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
When debugging after pycharm remote server is connected, trying to add breakpoint to file that does not exist: /data appears_ sda/d:/segmentation
How many of the 10 most common examples of istio traffic management do you know?
Tips for using dm8huge table
Solution of storage bar code management system in food industry
Maxay paper latex template description
MySql数据库root账户无法远程登陆解决办法
Chinese brand hybrid technology: there is no best technical route, only better products
Comprehensive ability evaluation system
Lombok principle and the pit of ⽤ @data and @builder at the same time
Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
How can programmers resist the "three poisons" of "greed, anger and ignorance"?