F - Connecting Chips Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

FuriosaAI officially announced the mass production of its second-generation AI accelerator, the RNGD, this year. The RNGD is a product specialized for processing language models and multimodal models, delivering powerful computational performance while consuming minimal power.

Upon hearing the news of the RNGD chip’s mass production, Sorohue ordered N RNGD chips. Sorohue’s computer has (N+2M) slots arranged in a row, each capable of holding a single chip. Of these, 2M slots are occupied by M S-chips and M C-chips, respectively. Uniquely, the S-chips and C-chips require a single S-chip and a single C-chip to be connected via wires in order to function properly.

Sorohue decided to connect the S-chips and C-chips with wires until the ordered RNGD chips arrive. Since having too many wires crossing over empty slots makes it difficult to insert chips later, when connecting two chips with a wire, the wire must cross over at most one empty slot. It is not possible to remove and rearrange the S-chips and C-chips that are already inserted.

A string T representing the state of the slots is given. Find the number of distinct ways to connect the M pairs of chips installed in Sorohue’s computer using wires.

Two methods are considered distinct if, in one method, two chips are connected by a wire, whereas in the other method they are not.

Constraints

  • 1 \le N \le 10\,000
  • 1 \le M \le 10\,000
  • Let T be a string consisting of N occurrences of E, M occurrences of S, and M occurrences of C.
    • The ith character of T represents the type of chip inserted into the ith slot, where E indicates an empty slot, S indicates an S-chip, and C indicates a C-chip.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
T

Output

Print the number of ways to connect M pairs of chips with wires, modulo 998\,244\,353.

Sample Input 1

2 3
SECSCESC

Sample Output 1

4

Sample Input 2

4 1
ESEECE

Sample Output 2

0

Sample Input 3

6 11
ESSCESCCCESSCSCECCSCSESCSCES

Sample Output 3

31968

表示言語

/ /

점수 : 100 점

문제

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

RNGD 칩의 대량 생산 소식을 들은 소로휴는 RNGD 칩을 N개 주문했다. 소로휴의 컴퓨터에는 칩 하나를 꽂을 수 있는 슬롯 (N+2M)개가 나란히 있으며, 그중 2M개의 슬롯에는 S-칩과 C-칩이 각각 M개씩 꽂혀 있다. S-칩과 C-칩은 특이하게 S-칩과 C-칩을 정확히 하나씩 서로 전선으로 연결해야 올바르게 작동한다.

소로휴는 주문한 RNGD 칩이 올 때까지 모든 S-칩과 C-칩을 전선으로 연결하기로 했다. 빈 슬롯 위로 너무 많은 전선이 지나면 나중에 칩을 꽂기 어려워지기 때문에, 두 칩을 전선으로 연결할 때는 전선이 최대 하나의 빈 슬롯 위를 지나도록 연결해야 한다. 이미 꽂혀 있는 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

表示言語

/ /

配点 : 100 点

問題文

FuriosaAIは今年、第2世代AIアクセラレータ「RNGD」の量産を正式に発表した。RNGDは言語モデルおよびマルチモーダルモデルの処理に特化した製品であり、低消費電力でありながら強力な演算性能を提供する。

RNGDチップの量産ニュースを聞いたソロヒューは、RNGDチップをN個注文した。ソロヒューのコンピュータには、チップを1つずつ差し込めるスロットが(N+2M)個並んでおり、そのうち2M個のスロットには、SチップとCチップがそれぞれM個ずつ差し込まれている。SチップとCチップは、特異なことに、1つのSチップと1つのCチップを互いに配線で接続しなければ正しく動作しない。

ソロヒューは、注文したRNGDチップが届くまで、SチップとCチップを配線で接続することにした。空いているスロットの上を配線が通りすぎると、後でチップを挿しにくくなるため、2つのチップを配線で接続する際は、配線が最大1つの空いているスロットの上を通るように接続しなければならない。すでに挿されているSチップとCチップを抜いて再配置することはできない。

スロットの状態を表す文字列 T が与えられる。ソロヒューのコンピュータに挿されている M 組のチップを配線で接続する、互いに異なる方法の数を求めよう。

ある2つのチップが、ある方法では互いに配線で接続されているが、別の方法ではそうでない場合、その2つの方法は互いに異なるとする。

制約

  • 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