fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. typedef long long int ll;
  4. ll dp[22][22][1024];
  5. map <ll,ll> a1;
  6. ll e = 1000000007;
  7. void prime(ll n)  
  8. {  
  9.     while (n % 2 == 0)  
  10.     {  a1[2]++;
  11.         n = n/2;  
  12.     }  
  13.     for (int i = 3; i <= sqrt(n); i = i + 2)  
  14.     {  
  15.         while (n % i == 0)  
  16.         {  a1[i]++;
  17.             n = n/i;  
  18.         }  
  19.     }  
  20.     if (n > 2)
  21.     {
  22.         a1[n]++; }
  23. } 
  24. int main()
  25. {
  26.     map<ll,ll> a2;
  27.     a2[2]=0;
  28.     a2[3]=1;
  29.     a2[5]=2;
  30.     a2[7]=3;
  31.     a2[11]=4;
  32.     a2[13]=5;
  33.     a2[17]=6;
  34.     a2[19]=7;
  35.     a2[23]=8;
  36.     a2[29]=9;
  37.     ll n,m;
  38.     cin>>n>>m ; 
  39.     ll a[n+1][m+1];
  40.     ll i = 1 ; 
  41.     while(i<=n)
  42.     {
  43.         ll j=1;
  44.         while(j<=m)
  45.         {
  46.             cin>>a[i][j] ; 
  47.             j++;
  48.         }
  49.         i++;
  50.     }
  51.  
  52.     ll x = a[1][1] ; 
  53.  
  54.     prime(x);
  55.     ll sum  = 0 ; 
  56.     for (auto itr = a1.begin(); itr != a1.end(); ++itr) 
  57. { 
  58.      ll x = itr->first  ; 
  59.      ll y = itr->second ; 
  60.      if(y%2!=0)
  61.      {   ll hava  = a2[x]  ; 
  62.          ll good = (1<<hava);
  63.          sum = (sum^good);
  64.      }
  65.      else
  66.      {
  67.  
  68.      }
  69. }
  70.     dp[1][1][sum]=1;
  71.     a1.clear();
  72.     i=1;
  73.     while(i<=n)
  74.     {
  75.         ll j=1;
  76.         while(j<=m)
  77.         {
  78.  
  79.             if(i==1 && j==1)
  80.             {
  81.  
  82.             }
  83.             else
  84.             {
  85.                 ll x = a[i][j] ; 
  86.                  sum  = 0 ;prime(x); 
  87.  for (auto itr = a1.begin(); itr != a1.end(); ++itr) 
  88. { 
  89.      ll x = itr->first  ; 
  90.      ll y = itr->second ; 
  91.      if(y%2!=0)
  92.      {   ll hava  = a2[x]  ; 
  93.          ll good = (1<<hava);
  94.          sum = (sum^good);
  95.      }
  96. }
  97.  
  98.                 ll k = 0 ;
  99.                 while(k<=1023)
  100.                 {
  101.                     ll k1 = (sum^k);
  102.                     dp[i][j][k] = (dp[i-1][j][k1]%e + dp[i][j-1][k1]%e)%e;
  103.                     k++;
  104.                 }
  105.             a1.clear();}
  106.             j++;
  107.         }
  108. i++;
  109. }
  110.     cout<<dp[n][m][0];
  111.     return  0 ;
  112. }
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
3 2
1 1
3 1
3 1
stdout
copy 
2
https://ideone.com/bxhGuL
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!