阿祁的部落格

AtCoder Educational DP Contest pO. Matching 解題心得( 題目 )

解題概念:DP

解題方法:枚舉每個女生，利用位元的方式記錄目前選了哪一些男生，時間複雜度為O(2^N * N)。

Java參考程式碼(更好意見可留言於下方，謝謝!):

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

//Date:2022/02/23

import java.util.*;

import java.io.*;

public class Main {

    public static final int maxn=1<<21,mod=1000000007;

    public static long[] dp=new long[maxn];

    public static int[][] match=new int[21][21];

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

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

    public static int rd,ret;

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

        final int n=readint();

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

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

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

            }

        }

        dp[0]=1;

        int cnt;

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

            cnt=0;

            for(int j=(1<<(n-1));j>0;j>>=1) {

                if((j&i)==j) {

                    cnt++;

                }

            }

            for(int j=(1<<(n-1)),k=n-1;j>0;j>>=1,k--) {

                if((j&i)==j) {

                    if(match[k][cnt-1]==1) {

                        dp[i]+=dp[i^j];

                        dp[i]%=mod;

                    }

                }

            }

        }

        System.out.println(dp[(1<<n)-1]);

    }

    

    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;

    }

}