题目详情题解（0）讨论（0）提交记录（0）

AT_fps_24_k.順列

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数 NN。

考虑 (1,2,…,N)(1, 2, \dots, N) 的全排列 p=(p1,p2,…,pN)p = (p_1, p_2, \dots, p_N)。

请统计有多少个全排列满足如下条件，并将结果对 998244353998244353 取模后输出。

  • 对于每个 1≤i≤N−11 \leq i \leq N-1，都必须满足 max⁡(p1,p2,…,pi)≠i\max(p_1, p_2, \dots, p_i) \neq i。

输入格式

输入按以下格式从标准输入给出：

NN

输出格式

输出答案。

输入输出样例

  • 输入#1

    3

    输出#1

    3

  • 输入#2

    123456

    输出#2

    923416117

说明/提示

样例解释 1

有如下 33 个排列 pp 满足条件：

  • (2,3,1)(2,3,1)
  • (3,1,2)(3,1,2)
  • (3,2,1)(3,2,1)

数据范围

  • 1≤N≤2.5×1051 \leq N \leq 2.5 \times 10^5
  • NN 是整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页