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

AT_arc183_c.[ARC183C] Not Argmax

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

给定一个 $ (1,2,\cdots,N) $ 的排列 $ P=(P_1,P_2,\cdots,P_N) $，请计算满足以下 $ M $ 个条件的排列数量，并将答案对 $ 998244353 $ 取模。

  • 第 $ i $ 个条件：在 $ P_{L_i},P_{L_i+1},\cdots,P_{R_i} $ 这一段中，最大值不是 $ P_{X_i} 。其中，。其中， L_i,R_i,X_i $ 是输入给定的整数。

输入格式

输入从标准输入中给出，格式如下：

$ N $ $ M $ $ L_1 $ $ R_1 $ $ X_1 $ $ L_2 $ $ R_2 $ $ X_2 $ ⋯\cdots $ L_M $ $ R_M $ $ X_M $

输出格式

请输出满足条件的排列数量，对 $ 998244353 $ 取模后的结果。

输入输出样例

  • 输入#1

    3 2
1 3 2
1 2 1

    输出#1

    1

  • 输入#2

    5 1
1 1 1

    输出#2

    0

  • 输入#3

    10 5
3 8 4
3 10 4
1 7 2
1 8 3
3 8 7

    输出#3

    1598400

  • 输入#4

    15 17
2 11 9
2 15 13
1 14 2
5 11 5
3 15 11
1 6 2
4 15 12
3 11 6
9 13 10
2 14 6
10 15 11
1 8 6
6 14 8
2 10 2
6 12 6
3 14 12
2 6 2

    输出#4

    921467228

说明/提示

限制

  • $ 1\leq N\leq 500 $
  • $ 1\leq M\leq 10^5 $
  • $ 1\leq L_i\leq X_i\leq R_i\leq N $
  • 所有输入的值均为整数。

样例解释 1

满足条件的只有 $ P=(1,2,3) $ 这一种情况。

由 ChatGPT 4.1 翻译

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

首页