阿祁的部落格

Atcoder Beginner Contest 247 F - Cards 解題心得( 題目 )

解題概念:graph、連通塊

解題方法:本題可以把牌視為邊，連接兩個數字所形成的點，會形成許多連通塊，我們可以對於每個進行討論，發現數量1到4時分別有1、3、4、7種選法，後來發現其實他的關係很像費氏數列，只要先建表，之後DFS一次就好，時間複雜度為O(N)

//Author:En Chi Tsung(欉恩祁)

//Date:2022/04/13

import java.util.*;

import java.io.*;

public class Main {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static int ret,rd,cnt=0;

    public static long ans=1;

    public static final int mod=998244353;

    public static boolean neg;

    public static int[][] edge=new int[2][200005];

    public static int[] way=new int[200005];

    public static boolean[] vis=new boolean[200005];

    public static ArrayList<ArrayList<Integer>> e=new ArrayList<>();

    public static void main(String[] args) throws Exception{

        final int n=readint();

        for(int i=0;i<=n;i++) {

            e.add(new ArrayList<>());

        }

        for(int i=0;i<2;i++) {

            for(int j=0;j<n;j++) {

                edge[i][j]=readint();

            }

        }

        for(int i=0;i<n;i++) {

            e.get(edge[0][i]).add(edge[1][i]);

            e.get(edge[1][i]).add(edge[0][i]);

        }

        f();

        for(int i=1;i<=n;i++) {

            if(!vis[i]) {

                cnt=0;

                dfs(i);

                ans*=way[cnt];

                ans%=mod;

            }

        }

        System.out.println(ans);

    }

    

    public static void f() {

        way[1]=1;

        way[2]=3;

        for(int i=3;i<200005;i++) {

            way[i]=way[i-1]+way[i-2];

            way[i]%=mod;

        }

    }

    

    public static void dfs(int x) {

        vis[x]=true;

        cnt++;

        for(int i:e.get(x)) {

            if(vis[i])continue;

            dfs(i);

        }

    }

    public static int readint() throws Exception{

        ret=0;

        rd=br.read();

        while(rd>47&&rd<58) {

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}



class Pair{

    int x,y;

    Pair(int a,int b){

        x=a;

        y=b;

    }

}