結果

問題 No.1855 Intersected Lines
ユーザー chineristACchineristAC
提出日時 2022-02-25 23:47:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 783 ms / 2,000 ms
コード長 2,273 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 87,132 KB
実行使用メモリ 146,504 KB
最終ジャッジ日時 2023-09-16 19:23:10
合計ジャッジ時間 19,274 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
82,704 KB
testcase_01 AC 118 ms
82,988 KB
testcase_02 AC 119 ms
82,596 KB
testcase_03 AC 120 ms
82,548 KB
testcase_04 AC 128 ms
83,540 KB
testcase_05 AC 130 ms
83,452 KB
testcase_06 AC 129 ms
83,424 KB
testcase_07 AC 125 ms
83,364 KB
testcase_08 AC 709 ms
144,756 KB
testcase_09 AC 731 ms
145,692 KB
testcase_10 AC 729 ms
145,660 KB
testcase_11 AC 715 ms
145,600 KB
testcase_12 AC 730 ms
144,592 KB
testcase_13 AC 771 ms
145,728 KB
testcase_14 AC 768 ms
145,672 KB
testcase_15 AC 769 ms
145,424 KB
testcase_16 AC 750 ms
145,572 KB
testcase_17 AC 738 ms
145,528 KB
testcase_18 AC 747 ms
145,664 KB
testcase_19 AC 727 ms
145,560 KB
testcase_20 AC 734 ms
145,580 KB
testcase_21 AC 759 ms
145,736 KB
testcase_22 AC 761 ms
145,848 KB
testcase_23 AC 783 ms
146,060 KB
testcase_24 AC 774 ms
145,200 KB
testcase_25 AC 742 ms
146,416 KB
testcase_26 AC 732 ms
146,504 KB
testcase_27 AC 718 ms
145,280 KB
testcase_28 AC 121 ms
82,676 KB
testcase_29 AC 120 ms
82,816 KB
testcase_30 AC 122 ms
82,628 KB
testcase_31 AC 124 ms
82,832 KB
testcase_32 AC 120 ms
83,216 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