結果

問題 No.1855 Intersected Lines
ユーザー chineristAC
提出日時 2022-02-25 23:47:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 703 ms / 2,000 ms
コード長 2,273 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 143,504 KB
最終ジャッジ日時 2024-07-03 18:48:17
合計ジャッジ時間 16,277 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return (g1[n] * g2[r] % mod) * g2[n-r] % mod
mod = 998244353
N = 2*10**5
g1 = [1]*(N+1)
g2 = [1]*(N+1)
inverse = [1]*(N+1)
for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0
import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import e, log,gcd
input = lambda :sys.stdin.readline()
mi = lambda :map(int,input().split())
li = lambda :list(mi())
def cmb(n,r,_):
    if r < 0 or n < r:
        return 0
    res = g2[r]
    for i in range(r):
        res *= n-i
        res %= mod
    return res
mod = 998244353
N,M = mi()
color = []
for _ in range(M):
    c,v = input().split()
    color.append((c,int(v)))
R,B = 0,0
for c,v in color:
    if c=="R":
        R += v
    else:
        B += v
ALL_R = pow(R*(R-1)//2,mod-2,mod)*(R//2) % mod
ALL_B = pow(B*(B-1)//2,mod-2,mod)*(B//2) % mod
ALL_RB = ALL_R * ALL_B % mod
ALL_RR = pow(R*(R-1)*(R-2)*(R-3)//4,mod-2,mod) * (R//2) * ((R-2)//2) % mod
ALL_BB = pow(B*(B-1)*(B-2)*(B-3)//4,mod-2,mod) * (B//2) * ((B-2)//2) % mod
res = 0
memo = {"":1,"r":0,"b":0,"br":0,"rb":0,"brb":0,"rbr":0}
for c,v in color:
    if c=="R":
        res += (v * memo["brb"] % mod) * ALL_RB % mod
        res %= mod
        next_memo = {s:memo[s] for s in memo}
        for s in memo:
            if s=="" or s[-1]=="b":
                t = s + "r"
                if len(s)==3:
                    continue
                next_memo[t] += memo[s] * v % mod
                next_memo[t] %= mod
        memo = next_memo
    
    else:
        res += (v * memo["rbr"] % mod) * ALL_RB % mod
        res %= mod
        next_memo = {s:memo[s] for s in memo}
        for s in memo:
            if s=="" or s[-1]=="r":
                t = s + "b"
                if len(s)==3:
                    continue
                next_memo[t] += memo[s] * v % mod
                next_memo[t] %= mod
        memo = next_memo
    
#print(res * 5 % mod)
res += cmb(R,4,mod) * ALL_RR % mod
res += cmb(B,4,mod) * ALL_BB % mod
res %= mod
        
        
print(res % mod)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0