CompetitiveCoding-SoC-/square.cpp at master · kasangeri/CompetitiveCoding-SoC- · 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
#include<bits/stdc++.h>
using namespace std;


int A[71];
int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};
int bitmask[71];
int pow2[100000];
long dp[71][(1<<19)+1];
long long count(int num,int mask)
{
  if(num>70 && mask==0) return 1; //perfect square reached
  if(num>70 && mask!=0) return 0;
  int c = dp[num][mask];
  if (c!=-1) {
        return c;
    }
  if(A[num]==0) c = count(num+1, mask)%(1000000007);
  else
     {
       long long yo = pow2[A[num]-1];
       c = yo * count(num+1, mask)%(1000000007);
       c+= yo * count(num+1, mask^bitmask[num])%(1000000007);
     }
  dp[num][mask] = c;
  return c%(1000000007);

}


int main()
{
 int n;
 cin>>n;
 memset(dp, -1, sizeof dp);
 pow2[0]=1;
 for(int k=1;k<100000;k++) pow2[k] = (pow2[k-1])*2 % (1000000007);
 int ele;
 for(int i=0;i<n;i++){cin>>ele; A[ele]+=1;}
 for(int i=0;i<=70;i++)
  {
    int mask = 0;
    int cur = i;
    for(int j=0;j<19;j++)
    {
      // while(cur!=0)
          { while(cur%p[j]==0 && cur>0) {mask^=(1<<j); cur = cur/p[j];} }

    }
     bitmask[i] = mask;

  }

  cout<<count(1,0)-1<<endl;


// for(int i=0;i<70;i++)
  //cout<<bitmask[i];


}