B-一个板子题_牛客2026年愚人节比赛

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

是这样的，今天是愚人节，但是我是个很古板的人，我特别不喜欢这个节日，所以我决定来搞点破坏。

本题是个特别板子，特别没意思但又不简单的算法题，预估难度cf2000+，希望你能享受这个题，嘻嘻。

稍等哈，我来想想题面，是什么呢...要什么呢...唉呀有点没思路。要不这样吧，嗯，首先我们要有一个n，一个字符串，算点什么呢？来算个Z函数吧......然后再来个什么呢......再来一个排列吧。嗯，有了！

以下为本题的公式化题面

预估难度cf2000+ 😈

算个Z函数吧......

什么？完美排列？！

多重集 M(z) 怎么搞？

TLE警告 ⏱️

直接输出 NO 骗分咯 ~

注意时空限制哦！

我是个古板的人嘻嘻嘻

O(n) 能过吗？

给定一个整数 $n$ 和一个长度为 $n$ 的字符串 $S$ （下标从 $1$ 到 $n$ ），仅由小写英文字母组成。

首先，你需要计算该字符串的 Z 函数（Z-function）数组 $z$ 。

对于长度为 $n$ 的字符串 $S$ ，其 $z$ 函数是一个长度为 $n$ 的数组。其中 $z[i]$ （ $1 \le i \le n$ ）表示字符串 $S$ 与以 $S[i]$ 开头的后缀 $S[i \ldots n]$ 的最长公共前缀（LCP）的长度。特别地，在本题中我们规定 $z[1] = n$ 。

记数组 $z$ 中的所有元素构成的多重集为 $M(z)$ 。

我们称数组 $z$ 是一个“完美排列”，当且仅当 $M(z) = \{1, 2, \dots, n\}$ （即数组 $z$ 的元素恰好构成了 $1$ 到 $n$ 的一个排列）。

如果 $z$ 是一个“完美排列”，请计算：在保持多重集 $M(z)$ 元素不变的前提下，通过重新排列这些元素，可以生成多少个不同的序列？由于答案可能很大，请将结果对取模后输出。

如果 $z$ 不是“完美排列”，请直接输出 NO

温馨提示：请注意本题的时空限制。

感谢G题赞助的旋转效果QWQ

输出描述里面有模数和需要直接输出的东西

输入描述:

第一行包含一个整数 n（1 <= n <= 100000），表示字符串的长度。
第二行包含一个长度为 n 的字符串 S，保证仅由小写英文字母组成。

输出描述:

如果 z 是完美排列，输出一个整数，表示可能的排列序列数量对  取模的结果。
否则，输出字符串 NO。

示例1

输入

复制

3
aaa

输出

复制

说明

在样例 1 中，S = "aaa"。
i=1：后缀为 "aaa"，与 S 的 LCP 长度为 3，z[1] = 3。
i=2：后缀为 "aa"，与 S 的 LCP 长度为 2，z[2] = 2。
i=3：后缀为 "a"，与 S 的 LCP 长度为 1，z[3] = 1。
数组 z = [3, 2, 1]，其构成的多重集 M(z) = {1, 2, 3}，恰好是 1 到 3 的一个排列，满足“完美排列”的条件。
保持集合 {1, 2, 3} 不变进行重新排列，共有 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) 共 6 种不同的序列，对 模数 取模后依然是 6。

示例2

输入

复制

4
abac

输出

复制

NO

说明

在样例 2 中，S = "abac"。
z 数组的计算结果为 z = [4, 0, 1, 0]。
其多重集 M(z) = {0, 0, 1, 4}，不等于 {1, 2, 3, 4}。因此它不是完美排列，输出 NO。

示例3

输入

复制

5
ababa

输出

复制

NO

说明

在样例 3 中，S = "ababa"。
z 数组的计算结果为 z =[5, 0, 3, 0, 1]。不满足“完美排列”条件，输出 NO。