fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. import static java.lang.Math.max;
  4. import static java.lang.Math.min;
  5. import static java.lang.Math.abs;
  6. public class Main {
  7.     public static int mod = (int) 1e9 + 7;
  8.  
  9.     static class FastReader {
  10.         BufferedReader br;
  11.         StringTokenizer st;
  12.  
  13.         public FastReader() {
  14.             br = new BufferedReader(new InputStreamReader(System.in));
  15.         }
  16.  
  17.         String next() {
  18.             while (st == null || !st.hasMoreTokens()) {
  19.                 try {
  20.                     st = new StringTokenizer(br.readLine());
  21.                 } catch (IOException e) {
  22.                     e.printStackTrace();
  23.                 }
  24.             }
  25.             return st.nextToken();
  26.         }
  27.  
  28.         int nextInt() {
  29.             return Integer.parseInt(next());
  30.         }
  31.  
  32.         long nextLong() {
  33.             return Long.parseLong(next());
  34.         }
  35.  
  36.         double nextDouble() {
  37.             return Double.parseDouble(next());
  38.         }
  39.  
  40.         String nextLine() {
  41.             String str = "";
  42.             try {
  43.                 str = br.readLine().trim();
  44.             } catch (Exception e) {
  45.                 e.printStackTrace();
  46.             }
  47.             return str;
  48.         }
  49.     }
  50.  
  51.     static class FastWriter {
  52.         private final BufferedWriter bw;
  53.  
  54.         public FastWriter() {
  55.             this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
  56.         }
  57.  
  58.         public void print(Object object) throws IOException {
  59.             bw.append("" + object);
  60.         }
  61.  
  62.         public void println(Object object) throws IOException {
  63.             print(object);
  64.             bw.append("\n");
  65.         }
  66.  
  67.         public void println() throws IOException {
  68.             bw.append("\n");
  69.         }
  70.  
  71.         public void close() throws IOException {
  72.             bw.close();
  73.         }
  74.  
  75.         public void printLongArr(long[] arr) throws IOException {
  76.             for (long ele : arr) {
  77.                 print(ele + " ");
  78.             }
  79.             println();
  80.         }
  81.  
  82.         public void printIntArr(int[] arr) throws IOException {
  83.             for (int ele : arr) {
  84.                 print(ele + " ");
  85.             }
  86.             println();
  87.         }
  88.     }
  89.     public static long helper(int[][] mat,int mask,int size, long[]dp){
  90.         int student = Integer.bitCount(mask);
  91.         if( student>=size){
  92.             return 1;
  93.         }
  94.         if(dp[mask]!=-1){
  95.             return dp[mask];
  96.         }
  97.         long ans = 0;
  98.         for (int topic = 0; topic < size; topic++) {
  99.             int currentMask = 1<<topic;
  100.             if((mask&currentMask) == 0 && mat[student][topic]==1) {
  101.                 ans += helper(mat, mask | currentMask, size,dp);
  102.             }
  103.         }
  104.         return dp[mask]=ans;
  105.     }
  106.     public static void main
  107.             (String[] args) {
  108.         try {
  109.             FastReader fin = new FastReader();
  110.             FastWriter fout = new FastWriter();
  111.  
  112.             int t = fin.nextInt();
  113.             while(t-- > 0) {
  114.                 int n = fin.nextInt();
  115.                 int[][] likabilityMatrix = new int[n][n];
  116.                 for (int i = 0; i < n; i++) {
  117.                     for (int j = 0; j < n; j++) {
  118.  
  119.                         likabilityMatrix[i][j] = fin.nextInt();                    }
  120.             }
  121.                 long[] dp = new long [1<<(n + 1)];
  122.                     Arrays.fill(dp,-1);
  123.                 fout.println(helper(likabilityMatrix,0,n,dp));
  124.             }
  125.             fout.close();
  126.         } catch (Exception e) {
  127.             e.printStackTrace();
  128.             return;
  129.         }
  130.     }
  131. }
  132.  
Success #stdin #stdout 0.16s 57552KB
comments (?)
stdin
copy 
3
3
1 1 1
1 1 1
1 1 1
11
1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0 
11
0 1 1 1 0 1 0 0 0 1 0 
0 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 0 0 0 1 0 
0 1 0 1 0 1 0 1 0 1 1 
1 0 0 1 0 0 0 0 1 0 1 
0 0 1 0 1 1 0 0 0 0 1 
1 0 1 0 1 1 1 0 1 1 0 
1 0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 1 1 1 1 
0 1 0 0 0 0 0 0 0 1 1 
0 1 1 0 0 0 0 0 1 0 1
stdout
copy 
6
7588
7426
https://ideone.com/b1Iuyp
problem ASSIGN, based on SPOJ submission 35422655 (JAVA), 2025-12-30 00:10:20
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!