TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4945
  • Problem
  • P4945「雅礼集训 2018 Day4」Magic
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 5s 512m
    Description

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

    魔法纪元元年。

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

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

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

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

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

    桌面上摆放着 \(m\) 种魔术卡,共 \(n\) 张,第 \(i\) 种魔术卡数量为 \(a_i\),魔术卡顺次摆放,形成一个长度为 \(n\) 的魔术序列,在魔术序列中,若两张相邻魔术卡的种类相同,则它们被称为一个魔术对。

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

    Input Format

    第一行三个整数 \(m, n, k\)

    第二行 \(m\) 个正整数,第 \(i\) 个正整数表示 \(a_i\)

    Output Format

    一行一个整数表示答案。

    Sample Input 1

    3 5 1
    2 2 1

    Sample Output 1

    12

    Sample Input 2

    3 6 0
    1 2 3

    Sample Output 2

    10

    Sample Input 3

    2 100 20
    50 50

    Sample Output 3

    164333748

    Sample Input 4

    5 2333 666
    300 1000 233 200 600

    Sample Output 4

    119409616

    Sample Input 5

    5 30000 0
    4000 5000 6000 7000 8000

    Sample Output 5

    522962185

    Sample Input 6

    6 50000 12345
    9896 104 15000 13000 8000 4000

    Sample Output 6

    940147981

    Hint

    样例解释 1

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

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

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