计数
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小sun最近对计数问题来了兴趣，现在他有一个问题想问问你：
有一个含有n nn个数字的序列，每个数的大小是不超过1000 10001000的正整数，同时这个序列是个单调不增序列。但是很不幸的是，序列在保存过程中有些数字丢失了，请你根据上述条件，计算出有多少种不同的序列满足上述条件，答案对1000000007 10000000071000000007取模。（具体可以看样例）
输入描述：
第一行包含一个整数n nn，表示这个序列的长度。
第二行为n nn个整数a i a_iai，用空格隔开，如果数字是0 00，代表这个数字丢失了，其他的数字都在1 ˜ 1000 1 \~\ 10001˜1000之间
输出描述：
输出一行，表示答案。
示例1
输入：
3 9 0 8输出：
2示例2
输入：
2 5 4输出：
1示例3
输入：
3 0 0 0输出：
167167000备注：
1 ≤ n ≤ 1 e 6 1≤n≤1e61≤n≤1e6
0 ≤ a i ≤ 1000 0≤a_i≤10000≤ai≤1000
解题思路
本题将单调不增序列的缺失位填充问题转化为组合数学隔板法求解，核心是把m mm个连续缺失位的合法填充约束（前值p r e ≥ pre≥pre≥填充值≥ ≥≥后值c u r curcur，且填充值单调不增）通过变量替换转化为非负整数解问题，对应组合数C ( p r e − c u r + m , m ) C(pre-cur+m, m)C(pre−cur+m,m)；首先预处理阶乘和逆元（快速幂求逆元），用于O ( 1 ) O(1)O(1)计算组合数，初始化前值p r e = 1000 pre=1000pre=1000（填充数最大为1000 10001000）、连续缺失位m = 0 m=0m=0、答案a n s = 1 ans=1ans=1，遍历序列统计连续0 00的个数，遇非0 00数则计算该段0 00的组合数并累乘到答案，更新p r e prepre为当前数，补a [ n + 1 ] = 1 a[n+1]=1a[n+1]=1确保最后一段0 00被处理，若原序列非0 00数不满足单调不增则答案为0 00；阶乘预处理O ( n + 1000 ) O(n+1000)O(n+1000)、遍历O ( n ) O(n)O(n)，适配n ≤ 1 e 6 n≤1e6n≤1e6的规模，所有计算模1 e 9 + 7 1e9+71e9+7，精准统计合法序列数。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;constll M=1e3+10;ll fac[N],a[N];llqmi(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}returnres;}llcomb(ll n,ll m){returnfac[n]*qmi(fac[m]*fac[n-m]%p,p-2)%p;}voidcalc(ll n){fac[0]=1;for(ll i=1;i<n+M;++i)fac[i]=fac[i-1]*i%p;}intmain(){ll n;cin>>n;calc(n);for(ll i=1;i<=n&&cin>>a[i++];);ll pre=1000,cur,m=0;ll ans=1;a[n+1]=1;for(ll i=1;i<=n+1;++i){if(a[i]==0)m++;else{if(m){ans=ans*comb(m+pre-a[i],m)%p;m=0;}pre=a[i];}}cout<<ans<<endl;return0;}
