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

AT_jsc2019_final_f.Count Permutations Many Times

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

有一个长度为 NN 的数列 A0,A1,⋯ ,AN−1A_0,A_1,\cdots,A_{N-1}。请回答接下来的 QQ 个询问。

  • 第 ii 个询问（0≤i<Q0 \leq i < Q）：给定整数 Li,RiL_i,R_i（0≤Li<Ri≤N0 \leq L_i < R_i \leq N）。求满足下述条件的 (0,1,⋯ ,N−1)(0,1,\cdots,N-1) 的一个排列 p0,p1,⋯ ,pN−1p_0,p_1,\cdots,p_{N-1} 的个数：
    • 对于所有 jj（Li≤j<RiL_i \leq j < R_i），都有 pj≠Ajp_j \neq A_j。

由于答案可能非常大，请输出对 998244353998244353 取模的结果。

输入格式

输入以如下格式从标准输入给出。

NN QQ A0A_0 A1A_1 ⋯\cdots AN−1A_{N-1} L0L_0 R0R_0 L1L_1 R1R_1 ⋮\vdots LQ−1L_{Q-1} RQ−1R_{Q-1}

输出格式

输出 QQ 行。第 i+1i+1 行（0≤i<Q0 \leq i < Q）输出第 ii 个询问的答案，对 998244353998244353 取模。

输入输出样例

  • 输入#1

    3 6
0 0 0
0 1
0 2
0 3
1 2
1 3
2 3

    输出#1

    4
2
0
4
2
4

  • 输入#2

    3 6
0 1 2
0 1
0 2
0 3
1 2
1 3
2 3

    输出#2

    4
3
2
4
3
4

  • 输入#3

    10 10
7 9 4 8 0 6 7 8 9 8
0 5
4 7
3 10
7 10
7 9
4 9
0 3
6 9
4 9
1 3

    输出#3

    2170680
2656080
1712520
2620800
2943360
2170680
2656080
2656080
2170680
2943360

说明/提示

限制条件

  • 1≤N≤20001 \leq N \leq 2000
  • 0≤Ai≤N−10 \leq A_i \leq N-1
  • 1≤Q≤20001 \leq Q \leq 2000
  • 0≤Li<Ri≤N0 \leq L_i < R_i \leq N
  • 所有输入的值均为整数。

样例解释 1

以第 00 个询问为例，满足条件的排列有 (1,0,2)(1,0,2)、(1,2,0)(1,2,0)、(2,0,1)(2,0,1)、(2,1,0)(2,1,0) 共 44 种。

由 ChatGPT 4.1 翻译

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

首页