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

AT_abc199_e.[ABC199E] Permutation

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

请输出将 $ (1,\ 2,\ 3,\ \dots,\ N) $ 重新排列后得到的数列 $ a $，满足以下条件的方案数。

  • 对于所有满足 $ 1 \le i \le M $ 的整数 $ i $，在 $ a_1,\ a_2,\ a_3,\ \dots,\ a_{X_i} $ 中，不超过 $ Y_i $ 的数最多只能有 $ Z_i $ 个。

输入格式

输入按以下格式从标准输入读入。

$ N $ $ M $

$ X_1 $ $ Y_1 $ $ Z_1 $

$ X_2 $ $ Y_2 $ $ Z_2 $

$ X_3 $ $ Y_3 $ $ Z_3 $

$\vdots $

$ X_M $ $ Y_M $ $ Z_M $

输出格式

请输出答案。

输入输出样例

  • 输入#1

    3 1
2 2 1

    输出#1

    4

  • 输入#2

    5 2
3 3 2
4 4 3

    输出#2

    90

  • 输入#3

    18 0

    输出#3

    6402373705728000

说明/提示

限制条件

  • $ 2 \le N \le 18 $
  • $ 0 \le M \le 100 $
  • $ 1 \le X_i < N $
  • $ 1 \le Y_i < N $
  • $ 0 \le Z_i < N $
  • 输入中的所有值均为整数。

样例解释 1

满足条件的 $ a $ 有以下 $ 4 $ 种：

  • $ (1,\ 3,\ 2) $
  • $ (2,\ 3,\ 1) $
  • $ (3,\ 1,\ 2) $
  • $ (3,\ 2,\ 1) $

$ (1,\ 2,\ 3) $ 和 $ (2,\ 1,\ 3) $ 不满足条件，因为在 $ a_1,\ a_2 $ 中，不超过 $ 2 $ 的数有 $ 2 $ 个，不符合要求。

由 ChatGPT 4.1 翻译

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

首页