简单计数(count)

简单计数(count)

【问题描述】 知名音乐人小 C 准备作一首新曲送给大家,曲子中共有 n 个音 符。音符有m 种,同一种音符重复出现太多次会很单调,对于第i 种, 小 C 不希望它在曲子中的某一段连续出现超过ai 次。小 C 想知道,他 有多少种不同的作曲方案。两种方案不同,当且仅当某个位置上的音 符不同。

【输入格式】

第一行两个正整数n,m 。 第二行m 个正整数,第i 个表示ai 。

【输出格式】

输出一个非负整数,表示答案对 998244353 取模后的结果。

【样例输入】

3 3 1 2 3

【样例输出】

21

【数据范围】

对于 10%的数据,n,m ≤ 5;

对于 30%的数据,n,m ≤ 50;

对于 50%的数据,n,m ≤ 500;

对于 70%的数据,n,m ≤ 5000;

对于 100%的数据,ai ≤ n ≤ 5000 , m ≤10 ^ 5。

//题解正在撰写中。。。

原文地址:https://www.cnblogs.com/XjzLing/p/8509776.html