[ROIR 2023] 一个普通的字符串问题 (Day 2)

Luogu

IDLGP10101

Time1000ms

Memory512MB

DifficultyP6

2023Special JudgeROIR（俄罗斯）

在这个问题中，你将会得到 $Q$ 个由字符 `a`、`b` 和 `c` 组成的字符串，对于每个字符串，需要计算与它等效的由字符 `a`、`b` 和 `c` 组成的非空字符串的数量。由于这个数量可能非常大，所以要求对 $10^9 + 7$ 取余。 ## Input 第一行输入一个数 $G$，表示当前子任务的编号。在样例中 $G=0$，本题另设一个分值为 $0$ 的 Subtask 0 来存储样例数据。第二行输入一个整数 $q$。接下来 $q$ 行，每行一个字符串。 ## Output 对于每个字符串输出一行一个整数表示答案，记得取模 $10^9+7$。 [samples] ## Background 翻译自 [ROIR 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。如果对于任意长度为 $2$ 的字符串 $u$，字符串 $s$ 中 $u$ 的出现次数与字符串 $t$ 中 $u$ 的出现次数相同，则两个字符串 $s$ 和 $t$ 称为等效字符串。因此，字符串 `aaaba`、`abaaa` 和 `baaab` 彼此等效（字符串 `aa` 出现两次，字符串 `ab` 出现一次，字符串 `ba` 出现一次，字符串 `bb` 不作为子串出现），而字符串 `cff` 和 `ccf` 则不等效。一个字符串和它本身是等效的。 ## Note 样例说明： - 字符串 `abaa` 等效于字符串 `abaa`、`aaba`、`baab`； - 字符串 `abca` 等效于字符串 `abca`、`bcab`、`cabc`； - 字符串 `ccbca` 等效于字符串 `ccbca` 和 `cbcca`； - 字符串 `bacc` 只等效于字符串 `bacc`。本题使用捆绑测试。 $n_i$ 表示第 $i$ 个输入字符串的长度，$L$ 表示所有字符串的长度之和，$w$ 表示所有查询中最大（未取模）的答案。 | 子任务编号 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 输入数据与样例相同 | | $1$ | $11$ | $s$ 中不含 `c` | | $2$ | $13$ | $s$ 中 `a` 与 `c` 不相邻 | | $3$ | $11$ | $n_i\le13$ | | $4$ | $10$ | $L\le40$ | | $5$ | $9$ | $L\le60$ | | $6$ | $13$ | $L\le10^5,w\le100$ | | $7$ | $33$ | 无 | 对于 $100\%$ 数据，$1\le q\le10^5$，$L\le10^6$。

Samples

Input #1

0
4
abaa
abca
ccbca
bacc

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2023] 一个普通的字符串问题 (Day 2)",
    "description": {
      "content": "在这个问题中，你将会得到 $Q$ 个由字符 `a`、`b` 和 `c` 组成的字符串，对于每个字符串，需要计算与它等效的由字符 `a`、`b` 和 `c` 组成的非空字符串的数量。由于这个数量可能非常大，所以要求对 $10^9 + 7$ 取余。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10101"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在这个问题中，你将会得到 $Q$ 个由字符 `a`、`b` 和 `c` 组成的字符串，对于每个字符串，需要计算与它等效的由字符 `a`、`b` 和 `c` 组成的非空字符串的数量。由于这个数量可能非常大，所以要求对 $10^9 + 7$ 取余。\n\n## Input\n\n第一行输入一个数 $G$，表示当前子任务的编号。在样例中 $G=0$，本题另设一个分值为 $0$ 的 Subtask 0 来存储样例...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments