题解 | #计数#（含乘法逆元讲解）

我爱数学！我爱数学！我爱数学！

从前有一位老师说，如果你想学好一个学科，只需要每天早上醒来，大喊三遍你爱它。

所以说，数学到底是什么呢？

一路走来，她不断变换着样子。从前，她作为一门学科，伴随我们走完完整的学生时代。现在，她化为算法竞赛中的一个板块，藏匿在一道道题目描述中,等待着我们的造访。

我常认为，在算法竞赛的旅程中，数学是最艰难的试炼，但同时也是最具魅力的存在。如果说其他算法在对题目进行手术，那么数学则是在与题目静静交谈。

她只是温和地坐在那里，倾听规则流动的声音。通过那些看似杂乱无章的算式，去触碰题目最柔软的内心。

题面

小 sun 最近对计数问题产生了兴趣，现在他有一个问题想请你帮忙解决。

给定一个长度为 n 的整数序列，该序列满足以下条件：

序列是单调不增的；
每个元素都是不超过 1000 的正整数；
在存储过程中，部分数字遗失了，用 0 表示。

请你根据以上条件，计算有多少种不同的原始序列可能满足要求。

答案需要对 1000000007 取模。

思路

题意很明确，意思是我们需要向空缺的位置填上数字，使得序列在全局上单调不增，求总方案数。

不难发现这个问题在不连续的0之间是独立的，所以我们可以求得每段连续0的方案数，最后使用乘法原理相乘。

整理0区间

那么第一步就是整理出所有连续0的区间，这里使用双指针实现；

vector<pair<int, int>> yuna;
int st=0; a[0]=1000; a[n+1]=1;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n+1; i++) {
    if(a[i]) yuna.push_back({st+1, i-1}), st=i;
}

计算每段方案数

为了表述方便，对于每一段区间，我们把允许填入数字的范围记作 w，每段需要填充的长度记作 h：

int w=a[l-1]-a[r+1]+1, h=r-l+1;

我的第一种想法

我们有 w 种可以填入的数字，那么我们可以选择其中的 i 种填入，而余下的空位使用重复的值填充。

我们可以先使用组合数算出在不同的 i 时有多少种可能的组合，再使用隔板法确定当分块数为 i 时可能的分隔方案数。对于每一个 i，二者相乘即为总方案数。

for(int i=1; i<=h; i++) {
    //间隔为h-1，在分块数为i时，需要的隔板数为i-1
    cnt=(cnt+C(h-1, i-1)*C(w, i)%M)%M;
}
ans=ans*cnt%M;

AC后的思考

细细品味之后，我觉得我的解法还是有些许丑陋了。为什么要讨论 i 的情况呢，我的心路历程是，我只会求单调减的方案数()。我不确定大家高中是不是都有学单调不升的求法，但我确实没有学过。

当题目的条件为单调递减时，我们从可取的数字中任意取出一种组合，组合中的数组都一定互异。换句话说，排列方法与组合种类一一对应，那么每个区间的方案数即为 $C_w^h$ 。

对于选出的 w 个元素可以重复，取出组合数的意义不再能表示方案数，这样我就要像刚刚那样枚举 i 再求和了。

有没有什么更优雅的求法？

既然没法从每次取出的 h 个数的角度考虑，我们可以尝试从 w 的角度出发。

既然一个数字既可以没出现过，也可以出现很多次，那么我们可以考虑每个数字出现的次数。这时候你突然想起 h 的意义就可以是每个数字出现次数之和，这个时候问题就转化为了简单不定方程解的个数的求解(太好了高中学过这个())：

cnt_1 + cnt_2 + \dots + cnt_w = h \quad (cnt_i \ge 0)

那么问题就变成了数量上的隔板法：

ans=ans*C(w+h-1, h)%M;

优雅！(意满离)

虽然两种解法的最坏复杂度是一致的，但是我想，去思考不同的解法这件事本身应该是有意义的。

至于组合数

如果你没有学过组合数板子，这里可以简单介绍一下。

我们知道，组合数的公式为：

C_n^m = \binom{n}{m} = \frac{n!}{m!(n-m)!}

在这个公式中，阶乘我们可以 $O(n)$ 地预处理出来：

Fac[0]=1;
for(int i=1; i<=N-1; i++) {
    Fac[i]=Fac[i-1]*i;
}

然后代入组合数公式：

int C(int a, int b) {
    if(a<b) return 0;
    return Fac[a]/Fac[b]/Fac[a-b];
}

如果题目不要求对一个大数取模，那么到这里也就结束了。

然而，在模意义除法操作是不具有封闭性的。也就是说，在普通运算中 $(a / b) \pmod M$ 并不等于 $(a \pmod M) / (b \pmod M)$ 。这个时候我们就要引入乘法逆元。

乘法逆元

概念：模逆元

如果我们能为 $a$ 找到一个数 $inv(a)$ ，使得(注意是模意义下)一个数乘以 $inv(a)$ 的结果恰好等于其除以 $a$ ，我们就称 $inv(a)$ 为 $a$ 的模逆元。

那么组合数公式将会被转化成这样：

int C(int a, int b) {
    if(a<b) return 0;
    return Fac[a]*inv(Fac[b])%M*inv(Fac[a-b])%M;
}

引入的乘法逆元的概念，除法就可以像加法与乘法一样参与模运算了。

求解方法：费马小定理

关于 $inv(a)$ ，这里使用费马小定理求解，你可以简单地理解为这是一个数学公式，记住就好了：

a^{-1} \bmod p = a^{p-2} \bmod p

换句话说， $a$ 在模 $p$ 意义下的逆元就等于 $a$ 的 $p-2$ 次幂，我们可以使用快速幂求解：

int inv(int a) {
    return qpow(a, p-2);
}

要注意的点是，费马小定理求解逆元仅适用于模数为素数时。不过对于此类对结果取模的题目而言，提供的模数一般均为素数(998244353, 1e9+7)。

附上代码

#include<bits/stdc++.h>
#include <climits>
using namespace std;
#define int long long
const int N=1000005;
const int M=1e9+7;
int n, a[N], Fac[N];
vector<pair<int, int>> yuna;
int qpow(int a, int b) {
    int ret=1;
    while(b) {
        if(b&1) ret=ret*a%M;
        a=a*a%M; b>>=1;
    }
    return ret;
}
int inv(int x) {
    return qpow(x, M-2);
}
int C(int a, int b) {
    if(a<b) return 0;
    return Fac[a]*inv(Fac[b])%M*inv(Fac[a-b])%M;
}
void solve() {
    cin>>n; int st=0; a[0]=1000; a[n+1]=1;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n+1; i++) {
        if(a[i]) yuna.push_back({st+1, i-1}), st=i;
    }
    int ans=1;
    for(auto &[l, r]: yuna) {
        if(l>r) continue;
        int w=a[l-1]-a[r+1]+1, h=r-l+1;
        ans=ans*C(w+h-1, h)%M;
    }
    cout<<ans;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    Fac[0]=1;
    for(int i=1; i<=N-1; i++) {
        Fac[i]=Fac[i-1]*i%M;
    }
    solve();
    // int T; cin>>T; while(T--) solve();
    return 0;
}

写在最后

这份题解写的比较详细，希望可以帮助到大家。特别是正在算法竞赛门槛前徘徊的同学，希望能为你CP旅途中的一盏小灯。

意满，离。