Public Judge

pjudge

Time Limit: 1.5 s Memory Limit: 256 MB Total points: 100

# 21778. 【PR #11】作业

统计

题目描述

今天是 YQH 的生日,她得到了 $n$ 个只包含小写字母的字符串 $s_i$ 作为生日礼物,第 $i$ 个字符串长度为 $a_i$。

YQH 对字符串非常感兴趣,她定义了函数 $f(s)$ 表示 $s$ 最小表示的开头元素的下标,下标从 $1$ 开始,如果有多个满足的元素则取下标最小的那个。例如,$f(\text{aaaa})=1,f(\text{babc})=2,f(\text{qweqweqwe})=3$,因为三个字符串的最小表示分别为 $\text{aaaa,abcb,eqweqweqw}$。如果你不知道最小表示法:请点击

YQH 的字符串是有魔力的,只要使用一个魔咒,每个 $s_i$ 会等概率随机变成所有长度为 $a_i$ 的只包含小写字母的 $26^{a_i}$ 个字符串的其中一个。每次使用魔咒后,YQH 想记录下 $f(s_i)$,然而,她有些马虎,记录的顺序从 $f(s_1),f(s_2),\dots,f(s_n)$ 变成了 $f(s_n),f(s_1),f(s_2),\dots,f(s_{n-1})$ ,即向右循环移位一步。

YQH 的朋友 MY 注意到了这一情况,每次使用魔咒后,他都数出了多少个位置上的数没有记录错,记为 $c$,显然有 $c=\sum_{i=1}^n [f(s_i)=f(s_{(i\bmod n) +1})]$。但是 MY 厌倦了这个过程,他准备直接求出 $c$ 的期望值。

聪明的你一定知道 $\sum_{i=1}^n [f(s_i)=f(s_{(i\bmod n) +1})]$ 的期望值了,请把这个数目告诉 MY 吧。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

输出一个整数表示 $c$ 的期望值对 $998244353$ 取模后的值。

样例

样例输入1

2
1 2

样例输出1

729486259

显然 $f(s_1)$ 恒为 $1$,$f(s_2)=1+[s_{2,1} > s_{2,2}]$,所以,$P([f(s_1)=f(s_2)])={351\over 676}$,所以 $E(\sum_{i=1}^n [f(s_i)=f(s_{(i\bmod n) +1})])={27\over 26}\equiv 729486259\pmod{998244353}$。

样例输入2

1
1000

样例输出2

1

显然 $f(s_1)$ 恒等于自身。

样例输入3

5
3 1 5 2 4

样例输出3

727907401

样例输入/输出4

见下发文件中 ex_hw4.inex_hw4.ans,样例 4 满足 $\text{subtask2}$ 的限制。

样例输入/输出5

见下发文件中 ex_hw5.inex_hw5.ans,样例 5 满足 $\text{subtask5}$ 的限制。

数据范围与提示

对于全部数据,保证 $1\le n,a_i\le 10^5$。

$\text{subtask1 10pts}$,$a_i\le 8$。

$\text{subtask2 20pts}$,保证 $a_i$ 全为质数。

$\text{subtask3 10pts}$,$n,a_i\le 1000$。

$\text{subtask4 20pts}$,$\sum a_i\le 10^5$。

$\text{subtask5 40pts}$,无特殊限制。

时间限制:$\texttt{1.5s}$

空间限制:$\texttt{256MB}$