結果

問題 No.1691 Badugi
ユーザー chineristACchineristAC
提出日時 2021-09-24 23:09:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,017 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 73,216 KB
最終ジャッジ日時 2024-07-05 11:25:55
合計ジャッジ時間 2,408 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
73,216 KB
testcase_01 AC 71 ms
72,960 KB
testcase_02 AC 71 ms
72,704 KB
testcase_03 AC 71 ms
73,216 KB
testcase_04 WA -
testcase_05 AC 74 ms
72,704 KB
testcase_06 AC 71 ms
72,752 KB
testcase_07 AC 70 ms
73,216 KB
testcase_08 AC 72 ms
72,960 KB
testcase_09 AC 73 ms
73,216 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 71 ms
73,088 KB
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,random

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

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 = 5*10**5 + 100
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

N,M,K = mi()

res = 0

"""
行-列-行
    |
    行

行... K-3 + 3
列... K-3 + 1
"""

res += cmb(N,K,mod) * cmb(K,3,mod) *  cmb(M,K-2,mod) * (K-2) * g1[K-3]
res %= mod

"""
行-列-行
    |
    行-列

行... K-4 + 3
列... K-4 + 2
"""

if 4<=K:
    res += cmb(N,K-1,mod) * cmb(K-1,3,mod) * 3 *  cmb(M,K-2,mod) * cmb(K-2,2,mod) * 2 * g1[K-4]
    res %= mod

"""
行-列-行-列
    |
    行-列

行... K-5 + 3
列... K-5 + 3
"""

if 5 <= K:
    res += cmb(N,K-2,mod) * cmb(K-2,3,mod) * 3 * cmb(M,K-2,mod) * cmb(K-2,3,mod) * 6 * g1[K-5]
    res %= mod


"""
列-行-列
    |
    列

行... K-3 + 1
列... K-3 + 3
"""

res += cmb(N,K-2,mod) * (K-2) * cmb(M,K,mod) * cmb(K,3,mod) * g1[K-3]
res %= mod

"""
列-行-列
    |
    列-行

列... K-4 + 3
行... K-4 + 2
"""

if 4<=K:
    res += cmb(M,K-1,mod) * cmb(K-1,3,mod) * 3 *  cmb(N,K-2,mod) * cmb(K-2,2,mod) * 2 * g1[K-4]
    res %= mod

"""
列-行-列-行
    |
    列-行

列... K-5 + 3
行... K-5 + 3
"""

if 5 <= K:
    res += cmb(N,K-2,mod) * cmb(K-2,3,mod) * 3 * cmb(M,K-2,mod) * cmb(K-2,3,mod) * 6 * g1[K-5]
    res %= mod



"""
・列-行-列 1 *a
・行-列-行 1 *b
・行-列-行-列 2 *c

a+b+c=2
行-列 * (K-2-a-b-2*c)
"""

coef = [1,1,3]
coef2 = [1,2,12]
for a in range(3):
    for b in range(3):
        for c in range(3):
            if a+b+c!=2 or (K-2-a-b-2*c) < 0 or (2*a+2*b+3*c+K-2-a-b-2*c)!=K:
                continue
                
            #print(a,b,c)
            
            gyo = a + 2 * b + 2 * c + (K-2-a-b-2*c)
            ret = 2*a + b + 2 * c + (K-2-a-b-2*c)

            tmp_g = cmb(N,gyo,mod) * cmb(gyo,a,mod) * cmb(gyo-a,2*b,mod) * coef[b] * cmb(gyo-a-2*b,2*c,mod) * coef2[c]
            tmp_r = cmb(M,ret,mod) * cmb(ret,2*a,mod) * (g1[2*a] * pow(inverse[2],a,mod)) * cmb(ret-2*a,b,mod) * g1[b] * cmb(ret-2*a-b,2*c,mod) * g1[2*c] * g1[ret-2*a-b-2*c]
            res += tmp_g * tmp_r % mod

            res %= mod

"""
行-列-行-列-行
列-行-列-行-列

行-列
｜ |
列-行

行-列 (K-4)
"""

if 4 <= K:
    tmp_1 = cmb(N,K-1,mod) * cmb(K-1,3,mod) * 3 * cmb(M,K-2,mod) * cmb(K-2,2,mod) * 2 * g1[K-4]
    tmp_2 = cmb(N,K-2,mod) * cmb(K-2,2,mod) * cmb(M,K-1,mod) * 6 * g1[K-4]
    tmp_3 = cmb(N,K-2,mod) * cmb(K-2,2,mod) * cmb(M,K-2,mod) * cmb(K-2,2,mod) * g1[K-4]
    res += tmp_1 + tmp_2 + tmp_3
    res %= mod

"""
行-列-行-列-行-列

行-列 K-5
"""

if 5 <= K:
    res += cmb(N,K-2,mod) * cmb(K-2,3,mod) * g1[3] * cmb(M,K-2,mod) * cmb(K-2,3,mod) * g1[3] * g1[K-5]
    res %= mod

print(res)
0