题目背景
众所周知,后缀数组可以用二分哈希在 O(nlog2n) 内求出,用倍增在 O(nlogn) 内求出,或者用高妙的手法在线性时间内求出,但是和这题没啥关系(也许有?)。
题目描述
一个字符串是一个长度为 n、元素均为 [1,m] 内正整数的序列 a1,a2,…,an。它的长度为 k 的后缀是 an−k+1,…,an。
将 n 个后缀按照字典序从小到大排序。记长度为 i 的后缀在所有后缀中字典序第 bi 小,则 b1,b2,…,bn 称为这个字符串的后缀数组。
给定 c1,c2,…,cm,考虑所有满足数字 i 出现次数不超过 ci 的长度为 n 的字符串。求它们有多少种本质不同的后缀数组,答案对 109+7 取模。两个后缀数组不同,当且仅当至少有一个位置的值不同。
输入格式
第一行包含两个正整数 n,m,表示字符串长度和字符种类数。
第二行包含 m 个非负整数 c1,c2,…,cm。
输出格式
输出一个整数,表示答案对 109+7 取模的结果。
样例
3 2
2 2
5
10 5
2 3 4 3 2
1003811
数据范围
对于所有数据,1≤n,m≤500,0≤ci≤n,∑i=1mci≥n。
| 测试点 |
额外限制 |
| 1-2 |
n,m≤5 |
| 3-5 |
n≤60,m=2 |
| 6 |
n≤60,m=3 |
| 7-9 |
n≤60,m≤50 |
| 10-14 |
n,m≤200 |
| 15-20 |
n,m≤500 |