#1625. 「雅礼集训 2018 Day4」Magic

    ID: 1625 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学DFT(含 NTT)及FFT容斥原理组合计数雅礼集训2018

「雅礼集训 2018 Day4」Magic

题目描述

前进!前进!不择手段地前进!——托马斯 · 维德

魔法纪元元年。

1453 年 5 月 3 日 16 时,高维碎片接触地球。

1453 年 5 月 28 日 21 时,碎片完全离开地球。

1453 年,君士坦丁堡被围城,迪奥娜拉接触到四维泡沫空间,成为魔法师,最终因高维碎片消失失去魔力而身死。

为了改写这段历史,你不惜耗费你珍藏已久的魔术卡来回到魔法纪元元年。

在使用这些魔术卡之前,你却对它们的排列起了兴趣...

桌面上摆放着 mm 种魔术卡,共 nn 张,第 ii 种魔术卡数量为 aia_i,魔术卡顺次摆放,形成一个长度为 nn 的魔术序列,在魔术序列中,若两张相邻魔术卡的种类相同,则它们被称为一个魔术对。

两个魔术序列本质不同,当且仅当存在至少一个位置,使得两个魔术序列这个位置上的魔术卡的种类不同,求本质不同的恰好包含 kk 个魔术对的魔术序列的数量,答案对 998244353998244353 取模。

输入格式

第一行三个整数 m,n,km, n, k

第二行 mm 个正整数,第 ii 个正整数表示 aia_i

输出格式

一行一个整数表示答案。

样例 1

3 5 1
2 2 1
12

设三种颜色分别为 A,B,C\rm A, B, C,则合法的 1212 种方案分别为:(AABCB)\rm (AABCB)(ABBAC)\rm (ABBAC)(ABBCA)\rm (ABBCA)(ACABB)\rm (ACABB)(ACBBA)\rm (ACBBA)(BAABC)\rm (BAABC)(BAACB)\rm (BAACB)(BBACA)\rm (BBACA)(BCAAB)\rm (BCAAB)(BCBAA)\rm (BCBAA)(CABBA)\rm (CABBA)(CBAAB)\rm (CBAAB)

3 6 0
1 2 3
10
2 100 20
50 50
164333748
5 2333 666
300 1000 233 200 600
119409616
5 30000 0
4000 5000 6000 7000 8000
522962185
6 50000 12345
9896 104 15000 13000 8000 4000
940147981

数据范围与提示

测试点编号 mm nn kk 特殊性质
1 =2=2 300\leq 300 =1 = 1
2 =2 = 2
3
4
5 =3=3 16\leq 16
6
7 80\leq 80
8
9
10 100 \leq 100 100\leq 100 =0= 0 m=nm = n
11 2000 \leq 2000 5000\leq 5000
12
13
14
15
16
17 20000 \leq 20000 100000\leq 100000 =0= 0 aia_i均相等且 20\leq 20
18
19
20
21
22
23
24
25

对于 100%100 \% 的数据满足 $1 \leq m \leq 20000, 0 \leq k \leq n \leq 100000, \sum_{i = 1}^{m} a_i = n$。