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

AT_arc065_d.[ARC065F] シャッフル

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

有一个长度为 NN 的只包含 0 和 1 的字符串 SS。你需要按照以下方式，对每个 1≤i≤M1 \leq i \leq M，按 ii 的升序依次进行如下操作：

  • 将 SS 的第 lil_i 个字符到第 rir_i 个字符（从左到右数）组成的子串，任意重新排列。

其中，lil_i 是非递减的。

请你求出经过 MM 次操作后，SS 可能出现的不同字符串的数量，结果对 1000000007(=109+7)1000000007 (=10^9+7) 取模。

输入格式

输入通过标准输入给出，格式如下：

NN MM SS l1l_1 r1r_1 : lMl_M rMr_M

输出格式

输出经过 MM 次操作后，SS 可能出现的不同字符串的数量，对 10000000071000000007 取模。

输入输出样例

  • 输入#1

    5 2
01001
2 4
3 5

    输出#1

    6

  • 输入#2

    9 3
110111110
1 4
4 6
6 9

    输出#2

    26

  • 输入#3

    11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11

    输出#3

    143

说明/提示

限制条件

  • 2≤N≤30002 \leq N \leq 3000
  • 1≤M≤30001 \leq M \leq 3000
  • SS 只包含 0 和 1。
  • SS 的长度等于 NN。
  • 1≤li<ri≤N1 \leq l_i < r_i \leq N
  • li≤li+1l_i \leq l_{i+1}

样例解释 1

第一次操作后，SS 可能出现的字符串有 01001、00101、00011，共 33 种。第二次操作后，SS 可能出现的字符串有 01100、01010、01001、00011、00101、00110，共 66 种。

由 ChatGPT 4.1 翻译

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

首页