Question

2327. 知道秘密的人数

English Version

题目描述

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

 

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

 

提示：

• 2 <= n <= 1000
• 1 <= delay < forget <= n

解法

方法一：差分数组

差分数组 $d[i]$ 记录每天知道秘密的人数变化情况，$cnt[i]$ 记录第 $i$ 天新得知秘密的人数。那么从 $[i+delay,i+forget)$ 的这段时间内，$cnt[i]$ 个人每天都能分享给另外 $cnt[i]$ 个人。

最终 $sum(d[:n+1])$ 就是答案。

时间复杂度 $O(n^2)$。

class Solution:
  def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
    m = (n << 1) + 10
    d = [0] * m
    cnt = [0] * m
    cnt[1] = 1
    for i in range(1, n + 1):
      if cnt[i]:
        d[i] += cnt[i]
        d[i + forget] -= cnt[i]
        nxt = i + delay
        while nxt < i + forget:
          cnt[nxt] += cnt[i]
          nxt += 1
    mod = 10**9 + 7
    return sum(d[: n + 1]) % mod

class Solution {
  private static final int MOD = (int) 1e9 + 7;

  public int peopleAwareOfSecret(int n, int delay, int forget) {
    int m = (n << 1) + 10;
    long[] d = new long[m];
    long[] cnt = new long[m];
    cnt[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (cnt[i] > 0) {
        d[i] = (d[i] + cnt[i]) % MOD;
        d[i + forget] = (d[i + forget] - cnt[i] + MOD) % MOD;
        int nxt = i + delay;
        while (nxt < i + forget) {
          cnt[nxt] = (cnt[nxt] + cnt[i]) % MOD;
          ++nxt;
        }
      }
    }
    long ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans = (ans + d[i]) % MOD;
    }
    return (int) ans;
  }
}

using ll = long long;
const int mod = 1e9 + 7;

class Solution {
public:
  int peopleAwareOfSecret(int n, int delay, int forget) {
    int m = (n << 1) + 10;
    vector<ll> d(m);
    vector<ll> cnt(m);
    cnt[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (!cnt[i]) continue;
      d[i] = (d[i] + cnt[i]) % mod;
      d[i + forget] = (d[i + forget] - cnt[i] + mod) % mod;
      int nxt = i + delay;
      while (nxt < i + forget) {
        cnt[nxt] = (cnt[nxt] + cnt[i]) % mod;
        ++nxt;
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + d[i]) % mod;
    return ans;
  }
};

func peopleAwareOfSecret(n int, delay int, forget int) int {
  m := (n << 1) + 10
  d := make([]int, m)
  cnt := make([]int, m)
  mod := int(1e9) + 7
  cnt[1] = 1
  for i := 1; i <= n; i++ {
    if cnt[i] == 0 {
      continue
    }
    d[i] = (d[i] + cnt[i]) % mod
    d[i+forget] = (d[i+forget] - cnt[i] + mod) % mod
    nxt := i + delay
    for nxt < i+forget {
      cnt[nxt] = (cnt[nxt] + cnt[i]) % mod
      nxt++
    }
  }
  ans := 0
  for i := 1; i <= n; i++ {
    ans = (ans + d[i]) % mod
  }
  return ans
}

function peopleAwareOfSecret(n: number, delay: number, forget: number): number {
  let dp = new Array(n + 1).fill(0n);
  dp[1] = 1n;
  for (let i = 2; i <= n; i++) {
    let pre = 0n;
    for (let j = i - forget + 1; j <= i - delay; j++) {
      if (j > 0) {
        pre += dp[j];
      }
    }
    dp[i] = pre;
  }
  let pre = 0n;
  let i = n + 1;
  for (let j = i - forget; j < i; j++) {
    if (j > 0) {
      pre += dp[j];
    }
  }
  return Number(pre % BigInt(10 ** 9 + 7));
}