AT_arc183_c [ARC183C] Not Argmax
题目描述
给定一个 $ (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\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 翻译