#PQZ1097x5448. 另一个欧拉数问题

    ID: 2522 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>QOJ官方数据QOJ公开样例级数据-覆盖不足来源赛事1097动态规划

另一个欧拉数问题

另一个欧拉数问题

题目描述

标题: 另一个欧拉数问题 - Problem - QOJ.ac

#5448. 另一个欧拉数问题

Statistics

The problem was used in the following contests:

题目背景

你继续向前走,遇到了一个身着黑袍的老人,那边的门前放着一个巨大的沙盘,老人用手中的树枝在沙盘前画着奇怪的符号。

老人告诉你,他从年轻开始便梦想一个问题,直到他垂垂老矣,似乎也只揭露了答案的一角。

或许我该将它们交给你们了,老人说。

别太担心,我不想太为难你,至少我已经把必要的工具给你准备好了。

题目描述

对于正整数 α,考虑下述长为 αn 的序列 a:

  • 对于每个 k=1,…,n,序列 a 中出现了恰好 α 个 k。
  • 对于 i<j 满足 ai=aj,那么对任意 i<k<j,有 ak≥ai。

我们称满足上述要求的序列是一个 (n,α) 阶排列。

现在输入一个 (n0,α) 阶排列 P。又给定 n 和 m,请你计算有多少 (n,α) 阶排列包含子序列 P,并且满足:

  • 总共有 m 个下标 i 满足 ai>ai+1。

你只需计算出这样的序列总数对 998244353 取模的结果。

输入格式

第一行输入四个整数 α,n,m,n0。

第二行输入 αn0 个正整数,保证构成一个 (n0,α) 阶排列。

输出格式

输出一个整数,表示满足要求的序列的数量。

样例一

input

1 4 2 2
2 1

output

7

样例二

input

2 4 2 2
1 2 2 1

output

19

子任务

对于 10% 的数据,保证 n≤2000。

对于另外 10% 的数据,保证 α=1,n0=1。

对于另外 30% 的数据,保证 α=1。

对于另外 15% 的数据,保证 α=2,n0=1。

对于另外 15% 的数据,保证 α=2。

对于 100% 的数据,保证 1≤n≤2×105,0≤m<n,1≤n0≤n,1≤αn0≤2×105。

提示

为了方便选手处理形式幂级数的运算,我们提供了一个模板。选手可以根据自己的需要参考与使用该模板,也可以不使用该模板。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

官方测试点 25 个;落地 2 个;时限 3.0s,内存 512MB。

样例

样例 1

1 4 2 2
2 1
7

样例 2

2 4 2 2
1 2 2 1
19

数据来源:QOJ 公开题包官方 .in/.out;本题落地 2 个测试点,QOJ 元数据标注官方共 25 点,覆盖级别:部分公开样例级数据。时限 3.0s,内存 512MB。按 Hydro 默认逐字节比对判定。