結果

問題 No.1855 Intersected Lines
ユーザー chineristACchineristAC
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
68,528 KB
testcase_01 AC 66 ms
68,000 KB
testcase_02 AC 62 ms
68,460 KB
testcase_03 AC 64 ms
68,452 KB
testcase_04 AC 74 ms
72,208 KB
testcase_05 AC 77 ms
74,004 KB
testcase_06 AC 74 ms
73,700 KB
testcase_07 AC 67 ms
71,528 KB
testcase_08 AC 665 ms
142,144 KB
testcase_09 AC 677 ms
141,984 KB
testcase_10 AC 685 ms
143,272 KB
testcase_11 AC 684 ms
142,740 KB
testcase_12 AC 697 ms
141,900 KB
testcase_13 AC 692 ms
142,516 KB
testcase_14 AC 690 ms
143,172 KB
testcase_15 AC 683 ms
142,624 KB
testcase_16 AC 696 ms
143,184 KB
testcase_17 AC 688 ms
143,180 KB
testcase_18 AC 668 ms
142,596 KB
testcase_19 AC 703 ms
143,308 KB
testcase_20 AC 682 ms
143,504 KB
testcase_21 AC 692 ms
143,292 KB
testcase_22 AC 677 ms
143,260 KB
testcase_23 AC 673 ms
141,492 KB
testcase_24 AC 680 ms
142,948 KB
testcase_25 AC 670 ms
141,460 KB
testcase_26 AC 666 ms
142,116 KB
testcase_27 AC 656 ms
142,752 KB
testcase_28 AC 61 ms
67,700 KB
testcase_29 AC 61 ms
67,476 KB
testcase_30 AC 60 ms
68,024 KB
testcase_31 AC 60 ms
68,484 KB
testcase_32 AC 61 ms
67,896 KB
権限があれば一括ダウンロードができます

ソースコード

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