← 返回题目列表

AtCoder · scpc2026_div1_f

F. 连接芯片

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

FuriosaAI今年正式宣布其第二代人工智能加速器RNGD量产。 RNGD是一款专门用于处理语言模型和多模态模型的产品,以极低的功耗提供强大的计算性能。

听到RNGD芯片量产的消息,索罗休下令 N RNGD 芯片。索罗休的电脑有 (N+2M) 插槽排列成一排,每个插槽能够容纳一个芯片。其中, 2M 插槽被占用 M S 芯片和 M C 芯片。独特的是,S 芯片和 C 芯片需要通过电线连接单个 S 芯片和单个 C 芯片才能正常运行。

Sorohue 决定用电线连接 S 芯片和 C 芯片,直到订购的 RNGD 芯片到达。由于过多的导线跨越空槽会导致后续插入芯片变得困难,因此当用导线连接两个芯片时,导线必须交叉 最多 1 个 空槽。无法移除和重新排列已插入的 S 芯片和 C 芯片。 给出了表示槽状态的

一个字符串 T 。找出连接的不同方式的数量 M 使用电线安装在 Sorohue 计算机中的芯片对。

如果在一种方法中两个芯片通过电线连接,而在另一种方法中则不然,则两种方法被认为是不同的。

约束

  • 1 \le N \le 10\,000
  • 1 \le M \le 10\,000
  • 让 T 是一个由以下组成的字符串 N 出现次数 E, M 出现次数 S,和 M 出现次数 C.
    • 的 i第一个字符 T 代表插入的芯片类型 i第一个槽位,其中 E 表示空槽, S 表示 S 芯片,并且 C 表示 C 芯片。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
T

输出

打印连接方式的数量 M 带线的芯片对,模数 998\,244\,353.


示例输入 1

2 3
SECSCESC

示例输出 1

4

示例输入 2

4 1
ESEECE

示例输出 2

0

示例输入 3

6 11
ESSCESCCCESSCSCECCSCSESCSCES

示例输出 3

31968

表示言語

/ /

점수 : 100 점

문제

FuriosaAI는 올해 공식적으로 2세대 AI fare속기 RNGD의 대량 생산을 발표했다. RNGD는 언어 모델 및 멀티모달 모델 처리에 특화된 제품으로, 적은 전력으로도 강력한 연산 성능을 제공한다。

RNGD 战队 RNGD 战队 N개 주문했다. 소로휴의 컴퓨터에는 칩 하나를 꽂을 수 있는 슬롯 (N+2M)개가 나란히 있으며, 그중 2M개의 슬롯에는 S-칩과 C-칩각각 M개씩 꽂혀 있다. S-칩과 C-칩은 특결해야 올바르게 작동한다。

RNGD 的配置为 S-칩과 C-칩을 전선으로 연결하기로 했다。 빈 슬롯 위로 너무 많은 전선 Been 지나면 나중에 칩을 꽂기 어려워지기 때문에, 두 칩을 전선으로 연결할 때는 전선 Been 최대 하나의 请注意以下事项。 꽂혀 있는 S-칩과 C-칩을 뽑아서 재배치할 수는 없다。

슬롯의 상태를 나타내는 문자열 T가 주어진다. 소로휴의 컴퓨터에 꽂혀 있는 M쌍의 칩을 전선으로 연결하는 서로 다른 방법의 수를 구해 보자.

어떤 두 칩이 한 방법에서는 서로 전선으로 연결되어 있는데 다른 방법에서는 그렇지 않은 경우 두 방법을 서로 다르다고 한다.

제한

  • 1 \le N \le 10\,000
  • 1 \le M \le 10\,000
  • T는 E N개, S M개, C M개로 구성된 문자열이다.
    • T의 i번째 문자는 i번째 슬롯에 꽂혀 있는 칩의 종류를 나타내며, E는 빈 슬롯, S는 S-칩꽂혀 있는 슬롯, C는 C-칩꽂혀 있는 슬롯을 의미한다.
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N M
T

출력

M쌍의 칩을 전선으로 연결하는 방법의 수를 998\,244\,353으로 나눈 나머지를 출력한다.


입력 예 1

2 3
SECSCESC

출력 예 1

4

입력 예 2

4 1
ESEECE

출력 예 2

0

입력 예 3

6 11
ESSCESCCCESSCSCECCSCSESCSCES

출력 예 3

31968