結果

問題 No.1855 Intersected Lines
ユーザー chineristACchineristAC
提出日時 2022-02-25 23:45:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,309 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 87,044 KB
実行使用メモリ 175,608 KB
最終ジャッジ日時 2023-09-16 19:20:44
合計ジャッジ時間 29,545 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

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
from turtle import right

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

print(R,B)

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)
0