33OJ
登录 注册

#P17540. 发迹

    ID: 20108 远端评测题 2500ms 512MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>数学洛谷原创O2优化组合数学排列组合逆元洛谷月赛根号分治

发迹

背景

:::epigraph[——《发迹》] 我种的种子从来没结果
我把自己关在家里
想要给自己点空间 :::

题目描述

定义一个包含 kk 种类型元素的序列 aa(下标从 11 开始)的一个重排的权值为其最长的满足如下条件的子区间 [L,R][L,R] 的长度:

  • L≠1L\ne 1。
  • ∀i∈[0,R−L],ai+1=ai+L\forall i\in[0,R-L],a_{i+1}=a_{i+L}。

特别地,如果没有满足条件的子区间,则重排的权值为 00。

Barry 有一个长度为 nn 的序列 aa,求序列 aa 的所有重排中,权值最小的重排数量对 998244353998244353 取模的值。两个重排不同,当且仅当存在一个位置上两个重排中元素的类型不同。

显然,序列初始的元素顺序对答案没有影响。所以为了减小输入量,我们将给你一个长度为 kk 的序列 cc,cic_i 表示序列中 ii 类型元素出现的次数,而上述问题中的 n=∑i=1kcin=\sum\limits_{i=1}^kc_i。

输入格式

本题包含多组测试。

第一行一个整数 TT,表示测试数据组数。对于每组测试数据:

第一行一个整数 kk,意义如题目所示。

接下来 kk 个用空格隔开的整数,表示出现次数序列 cic_i。

输出格式

输出 TT 行,每行一个整数,表示对应测试数据的答案。

3
1
5
3
2 3 2
10
1 2 3 4 5 6 7 8 9 10
1
148
648341419

提示

数据范围

本题开启捆绑测试。

对于 100%100\% 的测试数据,1≤T≤51\le T\le 5,1≤k≤2×1051\le k\le 2\times 10^5,1≤ci≤1071\le c_i\le 10^7,1≤n≤1071\le n\le 10^7。

子任务 k≤k\le n≤n\le 得分
1 88 1212
2 300300
3 30003000 1616
4 22 10710^7 88
5 30003000 2020
6 2×1052\times 10^5 2×1052\times 10^5 1212
7 10710^7 2020

后记

:::epigraph[——《发迹》] 真的 有数不清的遗憾
但现在看来觉得没什么
那天我流了很多泪
在那之后我告诉自己就不再轻易 cry :::