#2091. 萨菲克斯·阿瑞

    ID: 2091 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest129来源:qoj.ac数据:公开样例字符串组合数学后缀数组

萨菲克斯·阿瑞

萨菲克斯·阿瑞

题目描述

标题: 萨菲克斯·阿瑞 - Problem - QOJ.ac

#5697. 萨菲克斯·阿瑞

Statistics

The problem was used in the following contests:

小 P 来到了 NOIP2044 的赛场上,他发现第二题的题目是这样的:给你一个长度为 n 的字符串,该字符串由至多 m 种不同的字符组成,其中第 i 种字符的出现次数不超过 ci,问你这个字符串的后缀数组是什么。

聪明的小 P 想到了一个新的问题希望你来帮忙解答:在题目给定的限制下,能有多少种不同的答案。也就是所有由 m 种字符组成,其中第 i 种字符出现次数不超过 ci,且长度为 n 的字符串,共有多少种不同的后缀数组。

由于答案很大,你只用输出答案对 109+7 取模后的数。

对于一个字符串 s=s1s2...sn,记 suf(i) 表示 i 这个位置到末尾的子串。后缀数组为一个 1 到 n 的排列 p1,p2,...,pn,满足 suf(p1)<suf(p2)<⋯<suf(pn)。对于两个字符串 s 和 t,令 i 为第一个使得 si≠ti 的位置,那么我们 si 和 ti 中小的对应的字符串更小,如果 i 不存在,那么长度小的字符串更小。

对于字符串之间的大小关系,我们规定第 1 个字符最小,第 2 个字符次小,以此类推。

输入格式

输入的第一行包含两个正整数 n,m,表示字符串的长度为 n,共有 m 种字符。

接下来一行,包含 m 个非负整数 c1,c2,...,cm,表示每种字符最多的出现次数。保证 0≤c1,c2,...,cm≤n,c1+c2+...+cm≥n。

输出格式

输出共一行,包含一个正数,表示答案。

样例数据

样例 1 输入

3 2
2 2

样例 1 输出

5

样例 1 解释

我们记 a 为第一种字符,b 为第二种字符,那么共有 aab,aba,abb,baa,bab,bba 这六种可能的字符串。它们的后缀数组为

(1,2,3),(3,1,2),(1,3,2),(3,2,1),(2,3,1),(3,2,1).

所以共有 5 种不同的结果。

样例 2 输入

10 5
2 3 4 3 2

样例 2 输出

1003811

样例 3

见下发文件。

子任务

测试点编号nm约定 1≤6≤6无 2∼3≤10≤10 4≤500=2 5=3 6∼7≤500c1=c2=...=cm=n 8∼10≤50≤50无 11∼14≤200≤200 15∼20≤500≤500

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2
2 2
5

样例 2

10 5
2 3 4 3 2
1003811