核心内容摘要
qqc.iive十年沉淀，2025，未来已来，共赴新境
计数时间限制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≤1e60 ≤ 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-curm, m)C(pre−curm,m)首先预处理阶乘和逆元快速幂求逆元用于O ( 1 ) O(
O(
计算组合数初始化前值p r e 1000 pre1000pre1000填充数最大为1000
连续缺失位m 0 m0m
答案a n s 1 ans1ans1遍历序列统计连续0 00的个数遇非0 00数则计算该段0 00的组合数并累乘到答案更新p r e prepre为当前数补a [ n 1 ] 1 a[n1]1a[n1]1确保最后一段0 00被处理若原序列非0 00数不满足单调不增则答案为0 00阶乘预处理O ( n 1000 ) O(n
O(n
、遍历O ( n ) O(n)O(n)适配n ≤ 1 e 6 n≤1e6n≤1e6的规模所有计算模1 e 9 7 1e971e97精准统计合法序列数。
代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll p1e97;constll N1e610;constll M1e310;ll fac[N],a[N];llqmi(ll a,ll b){ll res1;while(b){if(b