「INOH」Round 1 - 狂气

Luogu

IDLGP9164

Time2333ms

Memory256MB

DifficultyP6

O2优化

有一个无限长的序列 $\{a\}$，**数组下标从 $1$ 开始**，初始 $a_1=1$，其余位置均为 $0$。 $m$ 次操作： 1. 对于所有**奇数** $i$，令 $a_{i+1}\gets a_{i+1}+a_i$。 2. 对于所有**偶数** $i$，令 $a_{i+1}\gets a_{i+1}+a_i$。你需要求出所有操作进行完之后的序列。为了方便输出，你只需要输出 $( \displaystyle\prod_{i = 1}^{m} (a_i + 1))\bmod 998244353$ 的值即可。 ## Input 第一行一个正整数 $m$。第二行一个长度为 $m$ 的字符串，表示操作序列。 ## Output 一行，表示 $( \displaystyle\prod_{i = 1}^{m} (a_i + 1)) \bmod 998244353$ 的值。 [samples] ## Note **样例 1 解释** 经过 5 次操作之后，序列前五项： $a_1 = 1$，$a_2 = 3$，$a_3 = 4$，$a_4 = 4$，$a_5 = 0$。 **本题采用捆绑测试**。 - Subtask 0（10pts）：$1 \le m \le 1000$。 - Subtask 1（20pts）：操作序列形如 $\tt121212\dots$。 - Subtask 2（20pts）：操作序列随机生成。 - Subtask 3（50pts）：无特殊限制。对于 $100\%$ 的数据，有 $1 \le m \le 2 \times 10^5$。 **请选手注意常数因子对运行效率的影响**

Samples

Input #1

5
11221

Output #1

Input #2

13
1122121212212

Output #2

400201782

API Response (JSON)

{
  "problem": {
    "name": "「INOH」Round 1 - 狂气",
    "description": {
      "content": "有一个无限长的序列 $\\{a\\}$，**数组下标从 $1$ 开始**，初始 $a_1=1$，其余位置均为 $0$。 $m$ 次操作： 1. 对于所有**奇数** $i$，令 $a_{i+1}\\gets a_{i+1}+a_i$。 2. 对于所有**偶数** $i$，令 $a_{i+1}\\gets a_{i+1}+a_i$。 你需要求出所有操作进行完之后的序列。 为了方便输出，你只需要输出 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2333,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9164"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个无限长的序列 $\\{a\\}$，**数组下标从 $1$ 开始**，初始 $a_1=1$，其余位置均为 $0$。\n\n$m$ 次操作：\n1. 对于所有**奇数** $i$，令 $a_{i+1}\\gets a_{i+1}+a_i$。\n2. 对于所有**偶数** $i$，令 $a_{i+1}\\gets a_{i+1}+a_i$。\n\n你需要求出所有操作进行完之后的序列。\n\n为了方便输出，你只需要输出 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments