题解 | 计数 # _牛客博客

$[思维+数学]$

将 $0$ 修改为 $1$ 到 $1000$ 的数字，求有多少种不递增序列

举一些例子后，发现解决这道题目的核心就是求：现在有连续为 $0$ 的长度为 $len$ ，然后可以填写的数字有 $num$ 个，求有多少种方案

可以填写的数字有 $num$ 个，化简为能填写 $1,2,3,...,num$ .

使用隔板法求求方案数：现在需要填写的格子有 $len$ ，可以填写的数字有 $num$ 个。

设 $cnt_{1}$ 表示数字 $1$ 填写的个数，...， $cnt_{num}$ 表示数字 $num$ 填写的个数。那么有：

$cnt_{i}\geq 0$
$\sum_{i=1}^{num}{cnt_{i}}=len$

方便点，将所有的 $cnt_{i}$ 加上 $1$ ，那么：

$cnt_{i}\geq 1$
$\sum_{i=1}^{num}{cnt_{i}}=len + num$

所以现在一共 $len+num$ 格子，有 $len+num-1$ 个间隔；一共有 $num$ 个数字，那么需要用 $num$ 隔板来分成 $num$ 个区块分别表示每个数字的使用个数

所以有 $C_{len+num-1}^{num-1}$ 种方案

因为 $len+num-1$ 最大可以达到 $10^{6}$ ，那么首先处理出阶乘数组......

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int mod = 1e9 + 7;
const int N = 1500000;

int f[N];

void init(){
    f[0] = 1;
    for(int i = 1; i <= 1400000;i ++) f[i] = (f[i - 1] * i) % mod;
}

int ksm(int a, int b, int p){
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum;
}

int work(int n, int m){
    int fz = f[n];
    int fm = (f[m] * f[n - m]) % mod;
    int sum = (fz * ksm(fm, mod - 2, mod)) % mod;
    return sum;
}
signed main(){
    HelloWorld;

    init();
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int left = 1000, right = 1, ans = 1;
    for(int i = 1; i <= n; i ++){
        if(a[i] == 0){
            if(i == 1) left = 1000;
            else left = a[i - 1];
            int len = 1;
            while(a[i + 1] == 0 && i <= n - 1) i ++, len ++;
            if(i == n) right = 1;
            else right = a[i + 1];
            int num = left - right + 1;
            ans = (ans * work(len + num - 1, num - 1)) % mod;
        }
    }
    cout << ans << endl;
    return 0;
}