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

AT_arc074_c.[ARC074E] RGB Sequence

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

有 NN 个格子横向排列成一行。格子从左到右依次编号为 11、22、…\ldots、NN。

Suknuke 君打算将每个格子涂成红色、绿色或蓝色中的一种颜色。根据 Suknuke 君的审美观，需要满足以下 MM 个条件。第 ii 个条件如下：

  • 第 lil_i 到第 rir_i 个格子（即 li,li+1,...,ril_i, l_i+1, ..., r_i）的颜色种类数恰好为 xix_i。

请问，有多少种格子上色的方案使得所有条件都得到满足？请输出方案数对 109+710^9+7 取模后的结果。

输入格式

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

NN MM l1l_1 r1r_1 x1x_1 l2l_2 r2r_2 x2x_2 :: lMl_M rMr_M xMx_M

输出格式

输出满足所有条件的上色方案数，对 109+710^9+7 取模后的结果。

输入输出样例

  • 输入#1

    3 1
1 3 3

    输出#1

    6

  • 输入#2

    4 2
1 3 1
2 4 2

    输出#2

    6

  • 输入#3

    1 3
1 1 1
1 1 2
1 1 3

    输出#3

    0

  • 输入#4

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

    输出#4

    108

说明/提示

限制条件

  • 1≤N≤3001 \leq N \leq 300
  • 1≤M≤3001 \leq M \leq 300
  • 1≤li≤ri≤N1 \leq l_i \leq r_i \leq N
  • 1≤xi≤31 \leq x_i \leq 3

样例解释 1

有如下 66 种方案：

  • RGB
  • RBG
  • GRB
  • GBR
  • BRG
  • BGR

其中，R / G / B 分别表示红色、绿色、蓝色的格子。

样例解释 2

有如下 66 种方案：

  • RRRG
  • RRRB
  • GGGR
  • GGGB
  • BBBR
  • BBBG

样例解释 3

有 00 种方案。

由 ChatGPT 5 翻译

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

首页