ABC247 F - Cards

atcoder.jp

【問題】
・N毎のカードが配られる。
・カードの表面には1~Nの数字が、裏面にも1~Nの数字が書かれる。
・全ての１～Nの数字が記載されたカードを選ぶ時の選び方は何通りか。

【考え方】
・表面と裏面に1回ずつ記載されるため、画数字は、2か所に記載されている。
・UnionFindなどを使って、カードを連結してるかどうかのグループに分ける。
・各グループ毎にDPを用いて、そのグループで何通りの選び方があるかを計算する。

from collections import deque

n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))

mod=998244353

tree=[[] for _ in range(n)]

for i in range(n):
    tree[p[i]-1].append(q[i]-1)
    tree[q[i]-1].append(p[i]-1)

from collections import deque

group=[]
check=[0]*n

for i in range(n):
    if check[i]==0:
        check[i]=1
        d = deque([i])
        tmp_group=set([])
        while d:
            tmp=d.popleft()
            tmp_group.add(tmp)
            for j in tree[tmp]:
                if check[j]==0:
                    d.append(j)
                    check[j]=1

        group.append(len(list(tmp_group)))

ans=1
for nn in group:
    if nn==1:
        ans=ans*1
    elif nn==2:
        ans=ans*3
    else:

        #dp[i][x]
        # x=1繋がっている x=0繋がっていない 
        dp_tunagi=[[0]*2 for _ in range(nn)]
        dp_tunagazu=[[0]*2 for _ in range(nn)]
        dp_tunagi[0][1]=1
        dp_tunagazu[0][0]=1
        
        

        for i in range(1,nn):
            dp_tunagi[i][0]+=dp_tunagi[i-1][1]%mod
            dp_tunagi[i][1]+=dp_tunagi[i-1][0]+dp_tunagi[i-1][1]%mod
            dp_tunagi[i][0]%=mod
            dp_tunagi[i][1]%=mod

            dp_tunagazu[i][0]+=dp_tunagazu[i-1][1]%mod
            dp_tunagazu[i][1]+=dp_tunagazu[i-1][0]+dp_tunagazu[i-1][1]%mod
            dp_tunagazu[i][0]%=mod
            dp_tunagazu[i][1]%=mod
        tmp=(dp_tunagi[-1][0]+dp_tunagi[-1][1]+dp_tunagazu[-1][1])%mod
        ans=ans*tmp%mod
        ans%=mod
       # print(dp_tunagi)
        #print(dp_tunagazu)
print(ans%mod)