#P18891. [2026多校联测]数组后缀

[2026多校联测]数组后缀

题目背景

众所周知,后缀数组可以用二分哈希在 O(nlog⁡2n)O(n\log^2 n) 内求出,用倍增在 O(nlog⁡n)O(n\log n) 内求出,或者用高妙的手法在线性时间内求出,但是和这题没啥关系(也许有?)。

题目描述

一个字符串是一个长度为 nn、元素均为 [1,m][1,m] 内正整数的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。它的长度为 kk 的后缀是 an−k+1,…,ana_{n-k+1},\ldots,a_n。

将 nn 个后缀按照字典序从小到大排序。记长度为 ii 的后缀在所有后缀中字典序第 bib_i 小,则 b1,b2,…,bnb_1,b_2,\ldots,b_n 称为这个字符串的后缀数组。

给定 c1,c2,…,cmc_1,c_2,\ldots,c_m,考虑所有满足数字 ii 出现次数不超过 cic_i 的长度为 nn 的字符串。求它们有多少种本质不同的后缀数组,答案对 109+710^9+7 取模。两个后缀数组不同,当且仅当至少有一个位置的值不同。

输入格式

第一行包含两个正整数 n,mn,m,表示字符串长度和字符种类数。

第二行包含 mm 个非负整数 c1,c2,…,cmc_1,c_2,\ldots,c_m。

输出格式

输出一个整数,表示答案对 109+710^9+7 取模的结果。

样例

3 2
2 2
5
10 5
2 3 4 3 2
1003811

数据范围

对于所有数据,1≤n,m≤5001\le n,m\le500,0≤ci≤n0\le c_i\le n,∑i=1mci≥n\sum_{i=1}^m c_i\ge n。

测试点 额外限制
1-2 n,m≤5n,m\le5
3-5 n≤60,m=2n\le60,m=2
6 n≤60,m=3n\le60,m=3
7-9 n≤60,m≤50n\le60,m\le50
10-14 n,m≤200n,m\le200
15-20 n,m≤500n,m\le500