結果

問題 No.2522 Fall in love, Girls!
ユーザー titiatitia
提出日時 2023-11-08 01:55:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 936 ms / 2,000 ms
コード長 2,029 bytes
コンパイル時間 430 ms
コンパイル使用メモリ 81,856 KB
実行使用メモリ 264,828 KB
最終ジャッジ日時 2023-11-08 01:55:22
合計ジャッジ時間 14,457 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 130 ms
214,816 KB
testcase_01 AC 131 ms
214,816 KB
testcase_02 AC 128 ms
214,816 KB
testcase_03 AC 607 ms
247,384 KB
testcase_04 AC 129 ms
215,200 KB
testcase_05 AC 129 ms
215,200 KB
testcase_06 AC 161 ms
227,292 KB
testcase_07 AC 169 ms
231,944 KB
testcase_08 AC 227 ms
248,896 KB
testcase_09 AC 202 ms
264,828 KB
testcase_10 AC 873 ms
264,300 KB
testcase_11 AC 190 ms
264,036 KB
testcase_12 AC 204 ms
264,828 KB
testcase_13 AC 874 ms
264,300 KB
testcase_14 AC 936 ms
264,828 KB
testcase_15 AC 909 ms
264,828 KB
testcase_16 AC 932 ms
264,828 KB
testcase_17 AC 461 ms
264,564 KB
testcase_18 AC 405 ms
264,828 KB
testcase_19 AC 432 ms
264,564 KB
testcase_20 AC 371 ms
264,300 KB
testcase_21 AC 369 ms
263,312 KB
testcase_22 AC 338 ms
264,036 KB
testcase_23 AC 422 ms
264,036 KB
testcase_24 AC 373 ms
260,476 KB
testcase_25 AC 184 ms
261,268 KB
testcase_26 AC 147 ms
237,476 KB
testcase_27 AC 185 ms
241,528 KB
testcase_28 AC 132 ms
221,144 KB
testcase_29 AC 291 ms
259,752 KB
testcase_30 AC 422 ms
263,840 KB
testcase_31 AC 321 ms
259,684 KB
testcase_32 AC 146 ms
235,544 KB
testcase_33 AC 233 ms
262,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,M,K=map(int,input().split())

mod=998244353

FACT=[1]
for i in range(1,2*10**6):
    FACT.append(FACT[-1]*i%mod)

E=[list(map(int,input().split())) for i in range(K)]

DEG=[-1]*(N+1)
EDGE=[[] for i in range(N+1)]

LIST=[]
for x,y in E:
    LIST.append(x)
    LIST.append(y)

    DEG[x]=max(0,DEG[x])
    DEG[y]=max(0,DEG[y])
    DEG[y]+=1
    EDGE[x].append(y)

LIST=sorted(set(LIST))
D={LIST[i]:i for i in range(len(LIST))}

ind_main=0
ind_sub=0

other_main=N-M
other_sub=M

for l in LIST:
    if l<=M:
        ind_sub+=1
        other_sub-=1
    else:
        ind_main+=1
        other_main-=1

Q=[]
for i in range(N+1):
    if DEG[i]==0:
        Q.append(i)

NEED=[0]*(len(LIST))

while Q:
    x=Q.pop()
    c=D[x]

    for to in EDGE[x]:
        DEG[to]-=1
        NEED[D[to]]|=((1<<c)|(NEED[D[x]]))

        if DEG[to]==0:
            Q.append(to)

if max(DEG)>0:
    print(0)
    exit()

DP=[0]*(1<<len(LIST))
DP[0]=1

DP2=[0]*(1<<len(LIST)) # startでindのものを使う。
DP2[0]=1
for i in range((1<<len(LIST))):
    for to in range(len(LIST)):
        if (1<<to) & i !=0:
            continue
        if (NEED[to] & i) == NEED[to]:
            DP[i|(1<<to)]+=DP[i]
            DP[i|(1<<to)]%=mod

            if i==0:
                if LIST[to]>M:
                    DP2[i|(1<<to)]+=DP2[i]
            else:
                DP2[i|(1<<to)]+=DP2[i]
            DP2[i|(1<<to)]%=mod

DP3=[0]*(other_main+other_sub+1)
DP3[0]=1

for i in range(len(LIST)):
    for j in range(1,other_main+other_sub+1):
        DP3[j]=(DP3[j]+DP3[j-1])%mod

ANS1=DP3[-1]*DP2[-1]*FACT[other_main+other_sub]%mod

if len(LIST)==0:
    ANS1=0
ANS2=0

if other_main>0:
    DP4=[0]*(other_main+other_sub)
    DP4[0]=other_main

    for i in range(len(LIST)+1):
        for j in range(1,other_main+other_sub):
            DP4[j]=(DP4[j]+DP4[j-1])%mod


    ANS2=DP4[-1]*DP[-1]*FACT[other_main+other_sub-1]%mod

print((ANS1+ANS2)%mod)
0