知道秘密的人数 图解题解

第 1 天只有 1 个人，第 6 天怎么就 5 个了

第 1 天有 1 个人知道秘密；每个学会秘密的人满 delay 天后开始每天分享给 1 个新人，学会满 forget 天彻底忘记。求第 n 天结束时还知道秘密的总人数，对 10^9+7 取模（取模只留除后余数，防装不下）。题面示例 n=6、delay=2、forget=4 时答案是 5。

一人一张档案挨个模拟，为什么撑不到第 n 天

逐个人头模拟——每人一张学会日档案，每天翻一遍看谁开讲、谁忘记。新人过 delay 天又拉新人，档案成倍往上堆，天数一多就翻不完。可档案里有用的只有学会日：学会日相同的人，开讲、忘记日全一样。

同一天学会的人，为什么能捆成一格记

按学会日分桶，动态规划（DP，把每天新学会几人存进表，用时直接查）里定义 dp[d] 为第 d 天新学会秘密的人数，这一格就是本题的状态。第 1 天只有最初那人，dp[1]=1 是种子。

窗口两端 d-forget+1 和 d-delay 从哪来

第 d 天新学会几人，等于当天正在开讲的人数（每人当天恰好教会 1 个新人）。谁在第 d 天开讲？学会日 j 得同时满足：首次分享日 j+delay ≤ d，即 j ≤ d-delay（右端）；还没忘 d ≤ j+forget-1，即 j ≥ d-forget+1（左端）。能开讲的人学会日恰好落在窗口 [d-forget+1, d-delay] 里。

转移（由前面的格子推出当前格的规则）就一句：dp[d] 等于窗口内所有 dp[j] 之和。窗口两端各错一格，数字立刻不对。

n=6、delay=2、forget=4，答案 5 怎么冒出来

dp[1]=1。第 2 天窗口 [2-4+1, 2-2]=[-1, 0]，全在第 1 天前，dp[2]=0。第 3 天窗口 [0, 1] 只有 dp[1]=1，dp[3]=1。第 4 天窗口 [1, 2]，dp[1]+dp[2]=1+0=1，dp[4]=1。第 5 天窗口 [2, 3]，dp[2]+dp[3]=0+1=1，dp[5]=1。第 6 天窗口 [3, 4]，dp[3]+dp[4]=1+1=2，dp[6]=2。

收答案：第 6 天记得秘密的，学会日落在 [6-4+1, 6]=[3, 6]，dp[3]+dp[4]+dp[5]+dp[6]=1+1+1+2=5，正是示例 1 的答案。

第 2 天窗口是 [-1, 0]，负下标一取会出什么事

每天把窗口里 forget-delay 个数相加是 O(n·(forget-delay))；窗口每天右移一格，改成维护一条滑动窗口和（右移时加新格、减掉滑出的格）可降到 O(n)。空间 O(n)，存整条 dp。

负下标要防：前几天窗口会伸到第 1 天之前，像第 2 天的 [-1, 0]，求和下界卡在 1、负下标按 0 算。取模也别漏：C++ 和 Java 每步取模、减法先补 mod 再取余，免得减出负数。答案那段用题面示例 2 复核：n=4、delay=1、forget=3 时 dp[2]+dp[3]+dp[4]=1+2+3=6（都按窗口和算：dp[2]=dp[1]=1、dp[3]=dp[1]+dp[2]=2、dp[4]=dp[2]+dp[3]=3）。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        const int mod = 1e9 + 7;
        int m = (n << 1) + 10;
        vector<long long> d(m), cnt(m);
        cnt[1] = 1;
        for (int i = 1; i <= n; i++) {
            if (cnt[i]) {
                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 long ans = 0;
        for (int i = 0; i <= n; i++) {
            ans += d[i];
        }
        return ans % mod;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        final int mod = (int) 1e9 + 7;
        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;
    }
}