結果

問題 No.2522 Fall in love, Girls!
ユーザー titiatitia
提出日時 2023-11-08 01:55:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,018 ms / 2,000 ms
コード長 2,029 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 264,960 KB
最終ジャッジ日時 2024-09-25 23:32:08
合計ジャッジ時間 15,634 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 183 ms
214,784 KB
testcase_01 AC 180 ms
214,400 KB
testcase_02 AC 186 ms
214,528 KB
testcase_03 AC 666 ms
247,712 KB
testcase_04 AC 194 ms
214,528 KB
testcase_05 AC 177 ms
214,656 KB
testcase_06 AC 217 ms
226,304 KB
testcase_07 AC 224 ms
231,040 KB
testcase_08 AC 285 ms
248,576 KB
testcase_09 AC 273 ms
264,960 KB
testcase_10 AC 944 ms
264,424 KB
testcase_11 AC 258 ms
264,048 KB
testcase_12 AC 270 ms
264,856 KB
testcase_13 AC 938 ms
264,448 KB
testcase_14 AC 996 ms
264,704 KB
testcase_15 AC 1,006 ms
264,832 KB
testcase_16 AC 1,018 ms
264,892 KB
testcase_17 AC 497 ms
264,596 KB
testcase_18 AC 474 ms
264,768 KB
testcase_19 AC 496 ms
264,576 KB
testcase_20 AC 435 ms
264,384 KB
testcase_21 AC 433 ms
263,180 KB
testcase_22 AC 408 ms
263,968 KB
testcase_23 AC 463 ms
264,092 KB
testcase_24 AC 439 ms
260,608 KB
testcase_25 AC 247 ms
261,288 KB
testcase_26 AC 204 ms
237,280 KB
testcase_27 AC 241 ms
240,640 KB
testcase_28 AC 183 ms
219,392 KB
testcase_29 AC 351 ms
259,712 KB
testcase_30 AC 487 ms
263,840 KB
testcase_31 AC 386 ms
259,700 KB
testcase_32 AC 201 ms
235,152 KB
testcase_33 AC 295 ms
262,400 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