Question

Cerința
Se dă o mulţime A formată din n elemente, numere naturale ( evident distincte ). Aflaţi câte submulţimi nevide ale lui A au suma elementelor număr par.

Date de intrare
Fișierul de intrare memory005.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte, separate prin spații, reprezentând elementele mulţimii A.

Date de ieșire
Fișierul de ieșire memory005.out va conține pe prima linie numărul S, reprezentând numărul submulţimilor nevide ale lui A care au suma elementelor număr par. Rezultatul se va afişa modulo 666013.

Restricții și precizări
1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi distincte şi mai mici decât 2.000.000.000

Answer 1

Răspuns:

#include <fstream>

using namespace std;

ifstream f("memory005.in");

ofstream g("memory005.out");

long long n,i,j,p,x,m,a[30] ;

int main()

{

   f>>n ;

   f>>x;

   i=1;

   while((i<n)&&(x%2==0))

       f>>x,i++;

   m=n-x%2;

   j=0 ;

   while(m!=0)

   {

      j++;

      a[j]=m%2 ;

      m=m/2 ;

   }

   p=1;

   for(i=j;i>=1;i--)

   {

       if(a[i]==1)

           p=(p*p*2)%666013;

       else

           p=(p*p)%666013 ;

   }

   p=(p-1)%666013 ;

   g<<p ;

   return 0;

}

Explicație: