2026.1.29每日一题：计数

题目来源：https://ac.nowcoder.com/acm/problem/52280

第一道能ac的2000分题，也是给咱切掉难题了哈。

题目大意

有一个长度为 n 的序列，序列中的每个数字都是 1 到 1000 之间的正整数，并且序列是单调不增的（即后一个数字不大于前一个数字）。不幸的是，序列中有些数字丢失了（用 0 表示）。你需要计算有多少种填充丢失数字的方式，使得填充后的序列满足单调不增的条件，并将答案对 1000000007 取模。

思路上来讲还算明确，由于这道题目总体的数据范围（备注： n 的范围到 1e6 ）比较小，所以直接扫描一遍数组的 O(n) 算法时间可以接受。

问题分析

因为序列必须单调不增，所以对于任意相邻的两个数字，都必须满足前一个大于等于后一个。我们可以将整个序列根据已知的非零数字划分成若干段连续的 0（丢失的数字）。对于每一段连续的 0，它们的取值范围由前后两个已知的非零数字决定。具体来说，假设一段连续的 0 前面最近的已知数字是 L，后面最近的已知数字是 R，这段 0 的长度为 k。那么我们需要为这 k 个位置填入数字 $x_1$ , $x_2$ ... $x_k$ ，使得：

$L \geq x_{1} \geq x_{2} \geq \dots \geq x_{k} \geq R$

这意味着每个 $x_i$ 都必须属于区间 [R, L]，并且整个子序列是非递增的。

关键转化

问题转化为：从区间 [R, L] 中可重复地选出 k 个整数，并将它们按非递增顺序排列，有多少种不同的选法？

实际上，一旦我们选出了这 k 个数字（允许重复），由于要求非递增排列，那么只有唯一的一种排列方式（从大到小排序）。因此，问题等价于：从 [R, L] 中可重复地选出 k 个数字，不考虑顺序，即求多重集的组合数。

区间 [R, L] 中共有 m = L - R + 1 个不同的整数。从 m 个元素中可重复地选取 k 个元素的组合数为：

$(\binom{m + k - 1}{k})$

这个公式称为“可重复组合数”或“星星与棒”模型。直观上，我们把 k 次选择想象成 k 颗星星，用 m-1 根棒子将星星分成 m 组，每组星星的数量对应该元素被选中的次数。因此方案数等于将 k 颗星星和 m-1 根棒子排列，即 $\binom{m + k - 1}{k}$ 。

在我们的问题中，m = L - R + 1，所以一段连续 0 的填充方案数为：

$(\binom{L - R + 1 + k - 1}{k}) = (\binom{L - R + k}{k})$

边界处理

如果序列开头有连续的 0，那么它们前面没有已知数字，我们可以认为上界 L = 1000（因为数字不超过 1000）。
如果序列末尾有连续的 0，那么它们后面没有已知数字，我们可以认为下界 R = 1（因为数字是正整数，最小为 1）。

为了方便统一处理，我们在序列的末尾额外添加一个数字 1（作为下界），并设序列开头之前的上界为 1000。

算法步骤

预处理组合数：计算阶乘和阶乘的逆元，以便 O(1) 查询组合数 $\binom{n}{m}$ 。
读入序列，并在序列末尾添加一个 1（代码中使用 a[n+1] = 1）。
初始化：pre = 1000 表示当前已知的上界，cnt0 = 0 表示当前连续 0 的个数，res = 1 存储答案。
遍历 i = 1 到 n+1：
- 如果 a[i] 非零：
  - 如果 cnt0 > 0，计算方案数：
    - sum = pre - a[i] + 1（即 L - R + 1）
    - 组合数 C(sum + cnt0 - 1, cnt0)，乘到 res 上。
  - 更新 pre = a[i]，cnt0 = 0。
- 否则（a[i] == 0）：cnt0++。
输出 res % 1000000007。

时间复杂度

预处理阶乘和逆元：O( $\max n$ )，其中 $\max n$ 为可能需要用到的最大阶乘索引（本题中我们预处理到 10^6）。
遍历序列：O(n)。
总时间复杂度：O(n + $\max n$ )，可以接受。

AC Code

// LANG:C++
// Auther:Hanzhi

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef __int128 lll;

typedef pair<ll,ll> P;

const int maxn=1e6+7;

const ll mod=1e9+7;

ll f[maxn],inf[maxn];

ll qpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

void init()
{
    f[0]=inf[0]=1;
    int N=1e6;
    for(int i=1;i<=N;i++) f[i]=(f[i-1]*i)%mod;
    inf[N]=qpow(f[N],mod-2);
    for(int i=N;i>=1;i--) inf[i-1]=(inf[i]*i)%mod;
}

ll cal(ll n,ll m)
{
    if(n<m) return 0;
    return f[n]*inf[m]%mod*inf[n-m]%mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    ll n;
    cin>>n;
    vector<ll> a(n+2);
    ll cnt0=0;
    ll res=1;
    ll pre=1000;
    for (ll i=1;i<=n;i++) cin >> a[i];
    a[n+1]=1;
    for( ll i=1;i<=n+1;i++ ) {
        if(a[i]) 
        {
            if(!cnt0) pre=a[i];
            else
            {
                ll sum=pre-a[i]+1;
                res=res*cal(sum+cnt0-1,cnt0)%mod;
                pre=a[i];
                cnt0=0;
            }
        }
        else cnt0++;   
    }
    cout<<res<<endl;
    return 0;
}