fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //#define _FILES
  6. #define PII pair<int,int>
  7. #define PB push_back
  8. #define SZ size()
  9. #define LEN length()
  10. #define LL long long
  11. const int MAXN = 1200005;
  12. const int MD = 1e9+7;
  13. bool isPrime[MAXN];
  14. int dp[505][200];
  15. vector<LL> pr;
  16. int G(LL x)
  17. {
  18.     int ans,cnt;
  19.     ans = 0;
  20.     for (int i=0;i<pr.size();i++)
  21.     {
  22.         if (pr[i]*pr[i]>x) break;
  23.         cnt = 0;
  24.         while (((x/pr[i])*pr[i])==x)
  25.         {
  26.             cnt++;
  27.             x/=pr[i];
  28.         }
  29.         ans+=cnt;
  30.     }
  31.     if (x>1) ans++;
  32.     return ans;
  33. }
  34. int main()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.  
  38.     #ifdef _FILES
  39.         freopen("","r",stdin);
  40.         freopen("","w",stdout);
  41.     #endif // _FILES
  42.     int n,g[505],ans;
  43.     LL x;
  44.     memset(isPrime,true,sizeof(isPrime));
  45.     for (int i=2;i<MAXN;i++)
  46.     {
  47.         if (!isPrime[i]) continue;
  48.         for (int j=2;j*i<MAXN;j++) isPrime[i*j] = false;
  49.         pr.PB(i);
  50.     }
  51.     cin>>n;
  52.     for (int i=1;i<=n;i++)
  53.     {
  54.         cin>>x;
  55.         g[i] = G(x);
  56.     }
  57.     memset(dp,0,sizeof(dp));
  58.     dp[0][0] = 1;
  59.     for (int i=1;i<=n;i++)
  60.     {
  61.         for (int j=0;j<200;j++)
  62.         {
  63.             dp[i][j] += dp[i-1][j];
  64.             if (dp[i][j]>=MD) dp[i][j] -= MD;
  65.             dp[i][j^g[i]] += dp[i-1][j];
  66.             if (dp[i][j^g[i]]>=MD) dp[i][j^g[i]] -= MD;
  67.         }
  68.     }
  69.     ans = 0;
  70.     for (int i=1;i<200;i++)
  71.     {
  72.         ans+=dp[n][i];
  73.         if (ans>=MD) ans-=MD;
  74.     }
  75.     cout<<ans<<endl;
  76.     return 0;
  77. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
3
1 4 8
stdout
copy 
6
https://ideone.com/W236dC
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years 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!