← 返回题目列表

AtCoder · fps_24_t

T. 多彩

中文机器翻译题面 查看原题

分数: 7 点

问题陈述

给你一个正整数序列 A = (A_1, A_2, \dots, A_N) 长度 N,和一个正整数 T.

有 \sum_{i=1}^N A_i 不同的位置。每个位置都涂上一个整数代表的颜色,并且正好有 A_i 涂有颜色的位置 i.

最初,您选择涂有颜色的位置之一 1,移动到该位置并标记它。然后,你完全重复以下操作 T 次:

  • 选择与当前位置颜色不同的任何位置,然后移动到那里。

计算一下有多少种方式,毕竟 T 操作后,您将回到最初标记的位置。输出结果取模 998244353.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数

部分分数

该问题有部分评分:

  • 如果您使用以下方法求解所有数据集 N \leq 3 \times 10^3,您将获得 5 点。

输入

输入由标准输入给出,格式如下:

N T
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

3 3
2 1 2

示例输出 1

4

让我们对位置进行如下标记:

  • 最初标记的位置:位置 1
  • 其他位置涂上颜色 1:位置 2
  • 涂有颜色的位置 2:位置 3
  • 两个位置涂上颜色 3:地点 4 和 5

那么,有 4 有效的移动顺序:

  • 1 \to 3 \to 4 \to 1
  • 1 \to 3 \to 5 \to 1
  • 1 \to 4 \to 3 \to 1
  • 1 \to 5 \to 3 \to 1

示例输入 2

10 31415926535897932
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

示例输出 2

66487687