The Lost Symbol

Luogu

IDLGP8946

Time3000ms

Memory512MB

DifficultyP7

2023洛谷原创O2优化

设二元运算符 $k\operatorname A n$ 为排列数 ${\rm A}_n^k$，$k \operatorname C n$ 为组合数 ${\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\textrm A,\textrm C$ 的序列 ${\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一个数都是 $[1,m]$ 中的整数的序列 $a_{[1,n]}$ 求 $(\cdots(((a_1\operatorname{opt}_1 a_2)\operatorname{opt}_2 a_3)\operatorname{opt}_3 a_4)\cdots\operatorname{opt}_{n-2}a_{n-1})\operatorname{opt}_{n-1}a_n$ 的和。答案对质数 $11417603$ 取模。 ## Input 第一行两个整数 $n,m$。接下来一行一个长度为 $n-1$ 的字符串表示 $\text{opt}$。 ## Output 一行一个整数表示答案。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/g4ofcg40.png) ## Note #### 【样例解释】对于样例 #1： $1\operatorname C 1=1$，$1\operatorname C 2=2$，$2\operatorname C 1=0$，$2\operatorname C 2=1$，求和为 $4$。对于样例 #2： $1\operatorname A 1=1$，$1\operatorname A 2=2$，$2\operatorname A 1=0$，$2\operatorname A 2=2$，求和为 $5$。 #### 【数据范围】不开启捆绑测试，按点给分。对于 $100\%$ 的数据，$2\leq n,m\leq 10^5$，${\rm opt}$ 仅包含 $\textrm A,\textrm C$。 | 测试点编号 | $n\leq$ | $m\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1\sim3$ | $8$ | $8$ | 无 | | $4\sim6$ | $314$ | $159$ | 无 | | $7\sim10$ | $2718$ | $2818$ | 无 | | $11\sim13$ | $10^5$ | $10^5$ | $\rm opt$ 仅由 $\rm A$ 构成 | | $14\sim16$ | $10^5$ | $10^5$ | $\rm opt$ 仅由 $\rm C$ 构成 | | $17\sim20$ | $10^5$ | $10^5$ | $\rm opt$ 由不超过 $10$ 段连续的 $\rm A$ 和连续的 $\rm C$ 拼接而成 | | $21,22$ | $8492$ | $10^5$ | 无 | | $23\sim25$ | $10^5$ | $10^5$ | 无 |

Samples

Input #1

2 2
C

Output #1

Input #2

2 2
A

Output #2

Input #3

8 8
CCACAAC

Output #3

API Response (JSON)

{
  "problem": {
    "name": "The Lost Symbol",
    "description": {
      "content": "设二元运算符 $k\\operatorname A n$ 为排列数 ${\\rm A}_n^k$，$k \\operatorname C n$ 为组合数 ${\\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。 给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\\textrm A,\\textrm C$ 的序列 ${\\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8946"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "设二元运算符 $k\\operatorname A n$ 为排列数 ${\\rm A}_n^k$，$k \\operatorname C n$ 为组合数 ${\\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。\n\n给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\\textrm A,\\textrm C$ 的序列 ${\\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments