結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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