Algorithm/Maximum AND Subsequences at master · TechRaY/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {


    static  long bigmod ( long a, long p, long m ) {                    //for getting the inverse factorial
        long res = 1 % m, x = a % m;

        while ( p>0 ) {
            if( ( p & 1)==1 ) res = ( res * x ) % m;
            x = ( x * x ) % m; p >>= 1;
        }

        return res;

    }

    static int mod=1000000007;
    static void solve(ArrayList<Long> giv,int n,int k){

         ArrayList<Long> al;
         int len;
         long rk=1;

        for(int b=62;b>=0;b--)
       {
            al=new ArrayList();

            len=giv.size();

          for(int i=0;i<len;i++)
          {
               if((((long)giv.get(i) & (rk<<b)))!=0)             //earlier i was shifting only integer 1 giving wrong ans it needs long 1 tp get AC
                {
                   al.add(giv.get(i));

                 //  System.out.print((long)giv.get(i) & (1<<b));
                }
          }


            if(al.size()>=k)
            {
                giv=al;


            }

      }

        long ans=giv.get(0);

         for(int i=1;i<k;i++)
        {
            ans=ans & giv.get(i);
        }

        System.out.println(ans);


         len = giv.size();
        long a = 1;
        for(int i=1; i<=len; i++)
        {
           a = (a*i)%(mod);
        }
        long b = 1;
        for(int i=1; i<=k; i++)
        {
           b = (b*i)%(mod);
        }
        long c = 1;
        for(int i=1; i<=(len-k); i++)
        {
           c = (c*i)%(mod);
        }

        b = bigmod(b, mod-2, mod);           //Inverse factorial concept    =========>>>>>   nCk=fact(n)*ifact(k)*ifact(n-k)
        c = bigmod(c, mod-2, mod);
        a = (a*b)%mod;
        a = (a*c)%mod;

        System.out.println(a);


    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();

         ArrayList<Long> giv=new ArrayList();

        for(int a_i=0; a_i < n; a_i++){
            giv.add(in.nextLong());
        }


        solve(giv,n,k);
    }
}