#1971. 简单计数

    ID: 1971 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest315来源:qoj.ac数据:公开样例动态规划

简单计数

简单计数

题目描述

标题: 简单计数 - Problem - QOJ.ac

#8465. 简单计数

Statistics

The problem was used in the following contests:

CauchySheep 近期优化了他的 快速数论变换(NTT) 模板的常数,现在他能在 0.1s 内轻松跑过 n=109 了,所以他准备用下面的这个简单计数题也考验一下你的常数优化水平。

传说,在很久很久以前,有一张 n 个点的带标号有向无环图。每条边有一个颜色,为 k 种不同颜色中的一种。这张图满足如下性质:

  • 每个点有不超过 1 条出边
  • 每个点的入边条数在集合 S 中

由于某种原因,你想知道这样的图的个数。由于这样的图可能很多,你只要输出答案对 998244353 取模的值。

两个图不同当且仅当存在一条从某个点 a 到某个点 b 的有向边,它只在恰好一个图中出现,或在两个图中都出现但颜色不同。

输入格式

第一行依次输入三个用空格分隔的正整数,n、k、|S|。

接下来第二行从小到大输入 |S| 个空格分隔的不同非负整数,表示 S 集合中的元素。

输出格式

输出一行一个 [0,998244352] 的整数,表示符合题意的图的个数对 998244353 取模的值。

样例数据

样例输入

3 1 2
0 1

样例输出

13

样例解释

有如下13个符合题意的图,其中 a→b 表示一条从 a 连向 b 的有向边:

  1. 没有边
  2. 1→2
  3. 2→1
  4. 1→3
  5. 3→1
  6. 2→3
  7. 3→2
  8. 1→2→3
  9. 1→3→2
  10. 2→1→3
  11. 2→3→1
  12. 3→1→2
  13. 3→2→1

样例输入

8 2 3
0 2 3

样例输出

7497953

样例输入

3000 2 3
0 1 3

样例输出

500207304

样例输入

876543210 233 4
0 1 2 3

样例输出

467638557

子任务

对于所有数据,1≤n≤9×108 ,1≤k≤107,S 集合非空,S 集合中所有元素为 [0,3] 的非负整数。

数据共分为 7 个子任务。

  • 子任务 1(5 分):n≤8。
  • 子任务 2(10 分):n≤5000。
  • 子任务 3(30 分):n≤105。
  • 子任务 4(20 分):n≤107。
  • 子任务 5(15 分):n≤108。
  • 子任务 6(10 分):S={0,1}。
  • 子任务 7(10 分):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 1 2
0 1
13

样例 2

8 2 3
0 2 3
7497953