SPOJ -> Multiples of 3

#include<bits/stdc++.h>
using namespace std;
int tree[400001][3];
int lazy[400001];
int query( int node , int  i , int  j , int s , int e )
{
           if(lazy[node] !=  0)
            {
               if( i!= j )
               {
                 lazy[2*node] = (lazy[node] + lazy[2*node])%3;
                 lazy[2*node+1] = ( lazy[node] + lazy[2*node+1])%3;
               }
               int a = tree[node][0];
               int b = tree[node][1];
               int c = tree[node][2];
               tree[node][1] = a;
               tree[node][2] = b;
               tree[node][0] = c;
               if(lazy[node] == 2)
               {
                   int a = tree[node][0];
                   int b = tree[node][1];
                   int c = tree[node][2];
                   tree[node][1] = a;
                   tree[node][2] = b;
                   tree[node][0] = c;
               }
               lazy[node] = 0;

            }

       if( i > j || s > j || e < i )
               return 0;

      if(s <= i && e >= j )
        return tree[node][0];

     return  query(2*node , i , (i+j)>>1 , s , e ) + query(2*node + 1 , ((i+j)>>1)+1 , j , s , e );

}
void update( int node , int  i , int  j , int s , int e )
{
            if(lazy[node] !=  0)
            {
               if( i!= j )
               {
                 lazy[2*node] = ( lazy[node] + lazy[2*node])%3;
                 lazy[2*node+1] = ( lazy[node] + lazy[2*node+1])%3;
               }
               int a = tree[node][0];
               int b = tree[node][1];
               int c = tree[node][2];
               tree[node][1] = a;
               tree[node][2] = b;
               tree[node][0] = c;
               if(lazy[node] == 2)
               {
                   int a = tree[node][0];
                   int b = tree[node][1];
                   int c = tree[node][2];
                   tree[node][1] = a;
                   tree[node][2] = b;
                   tree[node][0] = c;
               }
               lazy[node] = 0;

            }

       if( i > j || s > j || e < i )
               return;

      if(s <= i && e >= j )
      {
        int a = tree[node][0];
        int b = tree[node][1];
        int c = tree[node][2];
        tree[node][1] = a;
        tree[node][2] = b;
        tree[node][0] = c;
         if( i != j )
         {
           lazy[2*node] = ( 1 + lazy[2*node])%3;
           lazy[2*node+1] = ( 1 + lazy[2*node+1])%3;
         }
          return;
      }
       update(2*node , i , (i+j)>>1 , s , e );
       update(2*node + 1 , ((i+j)>>1)+1 , j , s , e );
       tree[node][0] = tree[2*node][0] + tree[2*node+1][0];
       tree[node][1] = tree[2*node][1] + tree[2*node+1][1];
       tree[node][2] = tree[2*node][2] + tree[2*node+1][2];



}
void build(int node , int i , int j )
{
      if( i > j )
       return;
     if(i == j)
      tree[node][0] = 1;
      else
      {
        build(2*node , i , (i+j) >> 1);
        build(2*node+1 , ((i+j) >> 1) + 1 , j);
        tree[node][0] = tree[2*node][0] + tree[2*node+1][0];
      }
}
int main(){


           int n , q;
           scanf("%d%d",&n,&q);

           build( 1 , 0 , n - 1);
        while( q-- )
        {
            int ch , l , r;
            scanf("%d%d%d",&ch,&l,&r);

            if(ch == 0)
            update( 1 , 0 , n - 1 ,  l , r );
            else
            printf("%d\n" , query( 1 , 0 , n - 1 , l , r ));


        }

        return 0;

}

SPOJ -> ARRAYSUB - subarrays

// sliding window algorithm
#include<bits/stdc++.h>
using namespace std;
int main(){


       int n , k , x ;
       cin >> n ;

       vector<int> vec;
       for(int i =  0 ; i < n ; ++i ){
          cin >> x;
          vec.push_back(x);
       }
       cin >> k;
        int mx = 0;
        vector<int> nval;
       for(int i =  0 ; i < n ; ++i ){

                  if(i%k == 0)
                   mx = vec[i];
                else
                mx = max( mx , vec[i] );
                nval.push_back(mx);
       }
       mx = 0;
       vector<int> val;
       for(int i = n-1 ; i >= 0 ; --i ){
             if(i%k == (k-1))
               mx = vec[i];
               else
               mx = max( mx , vec[i]);
               val.push_back(mx);

       }
       for(int i = 0 ; i < vec.size()-k+1  ; ++i )
             cout << max( nval[i+k-1] , val[val.size()-i-1]) <<" ";
             cout << endl;
             return 0;

}

SPOJ -> HORRIBLE - Horrible Queries

// using segmented tree with lazy update


#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
long long  vec[400001];
long long lazy[400001];
long long retreive( long long  id ,  long long   i , long long  j , long long  s , long long e)
{
     if(i > j || s > j || e < i )
        return 0;
       if(s <= i && e >= j )
        return vec[id];
        else
            {
            long long mid = (i+j)/2;
      vec[2*id+1]+=(mid-i+1)*lazy[id];
      vec[2*id+2]+=(j-mid)*lazy[id];
      lazy[2*id+1]+=lazy[id];
      lazy[2*id+2]+=lazy[id];
      lazy[id]=0;

       return retreive(2*id+1,i,mid,s,e)+retreive(2*id+2,mid+1,j,s,e);
        }
}
void update( long long id , long long  i , long long j , long long s , long long e , long long val )
{
     if(i > j || e < i || s > j )
        return;
     if(s <= i && e >= j )
     {
         vec[id]+=(j-i+1)*val;
          lazy[id]+=val;
     }
     else {
            long long mid = (i+j)/2;
      vec[2*id+1]+=(mid-i+1)*lazy[id];
      vec[2*id+2]+=(j-mid)*lazy[id];
      lazy[2*id+1]+=lazy[id];
      lazy[2*id+2]+=lazy[id];
      lazy[id]=0;
     update(2*id+1,i,mid,s,e,val);
     update(2*id+2,mid+1,j,s,e,val);
     vec[id]=vec[2*id+1]+vec[2*id+2];
     }
}
int main()
{
     int t;
     scanf("%d",&t);
    while(t--){
    memset(lazy,0,sizeof lazy);
    memset(vec,0,sizeof vec);
             long long n , c;
              scanf("%lld%lld",&n,&c);
                        while(c--)
              {
                 long long  ch , p , q , v;
                 scanf("%lld%lld%lld",&ch,&p,&q);
                 if(ch==0)
                 {
                     scanf("%lld",&v);
                     update(0,0,n-1,p-1,q-1,v);
                 }
                 else {
                        long long ans = retreive( 0 , 0 , n-1, p-1, q-1);
                    printf("%lld\n",ans);

                 }
              }



    }
      return 0;
}

SPOJ -> HORRIBLE - Horrible Queries

// using sqrt decomposition

#include<bits/stdc++.h>
using namespace std;
int main(){
                       int t;
                       scanf("%d",&t);
                       while(t--){
    long long n , q , ch , l , r ,v,t1,t2 ,i ;
         scanf("%lld%lld",&n,&q);
           long long  arr[n+1];
      memset(arr,0,sizeof arr);
      //  for(int i  = 0 ; i < n ; ++i )
        //   scanf("%lld",&arr[i]);
        long long val = sqrt(n);
        long long sz = (n-1)/val;
        long long sq[sz+1][3];
        memset(sq,0,sizeof sq);
       // for( i = 0; i < n ; ++i )
         //   sq[i/val][1]=(sq[i/val][1]+arr[i])%mod;
               while(q--)
               {
                    scanf("%lld%lld%lld",&ch,&l,&r);
                   l--;
                    r--;
                      if(ch == 0)
                      {
                          scanf("%lld",&v );
                           t1 = l/val;
                           t2 = r/val;
                          for( i = l ; i/val==t1 && i <= r ; ++i )
                          {
                                arr[i] = (arr[i] + v);
                                sq[t1][1] = (sq[t1][1]+v);
                          }
                          for( i = t1+1 ; i < t2 ; ++i )
                              sq[i][2] = (sq[i][2] + v);
                              if(t1 != t2 )
                              for(int i = r ; i/val==t2 && i>=l; --i )
                              {
                                  arr[i] = (arr[i] + v);
                                  sq[t2][1] = (sq[t2][1]+v);
                              }
                                        }
                      else
                      {
                          long long ans = 0;
                           t1 = l/val;
                           t2 = r/val;
                          for( i = l ; i/val==t1 && i <= r ; ++i )
                              ans = (ans + (arr[i] + sq[t1][2]));
                          for( i = t1+1 ; i < t2 ; ++i )
                            ans = (ans + (sq[i][1]+(sq[i][2]*val)));
                               if(t1 != t2 )
                              for( i = r ; i/val==t2 && i>=l; --i )
                              ans = (ans + (arr[i] + sq[t2][2]));
                              printf("%lld\n",ans);
                      }

               }
                       }
           return 0;
}

SPOJ -> FIBOSUM - Fibonacci Sum

#include<bits/stdc++.h>
#define  ll  long long
#define mod 1000000007
using namespace std;
void mul( ll a[2][2] , ll b[2][2])
{
   ll c[2][2];
   for(int i =  0 ; i < 2 ; ++i ){
      for(int j =  0 ; j < 2 ; ++j ){

          c[i][j] = 0;
          for(int  k = 0 ; k < 2 ; ++k )
            c[i][j] = (c[i][j] + (a[i][k]*b[k][j])%mod)%mod;
      }


   }
    for(int i = 0 ; i < 2 ; ++i ){
      for(int j  = 0 ; j < 2;  ++j )
        a[i][j] = c[i][j];
      }

}
ll fib( ll n)
{
        if(n==0)
         return 0;
         if(n == 1)
         return 1;
         ll res[2][2]={{1,0},{0,1}} , mat[2][2] = {{1,1} ,{1,0}};
             while(n)
             {
               if(n%2!=0)
               mul(res,mat);
               n = n >> 1;
               mul(mat,mat);

             }

           return res[0][1];
}
int main()
{
               int t;
               cin >> t;
               while(t--)
               {
                     ll n ,  m;
                     cin >> n  >> m;

                     ll ans = fib(m+2) - 1;
                      ans = ans  - (fib(n+1)-1);
                      if(ans<0)
                      ans+=mod;
                      ans = ans%mod;
                      cout << ans << endl;


               }
     return 0;
}

SPOJ -> A_W_S_N - Happy Valentine Day (Valentine Maze Game)

#include<bits/stdc++.h>
using namespace std;
int ans;
void cst(int ar[12][12],int node , int dest , int size , int cost,int vis[12],int collect)
{
      if(cost > ans )
      return;
      if(node == dest)
      {
          if(collect == size)
          {
                ans = min(ans,cost);
                return;
          }

      }

     for(int i = 1 ; i <= size ; ++i )
     {
         if(vis[i] == 0 && i != node)
         {
             vis[i] = 1;
            cst(ar,i,dest,size,cost+ar[node][i],vis,collect+1);
            vis[i] = 0;
          }
     }

}
int main(){
          ios_base::sync_with_stdio(false);
            int t;
           cin >> t;
           while(t--){

              int n  , m;
              cin >> n >> m;

                string x[n+1];
                for(int i = 0 ; i < n ; ++i )
                    cin >> x[i];

                 vector<int> graph[10001];
                       int source;
                       int dest;
                       vector<int> choc;
                 for(int i = 0 ;  i < n ; ++i ){
                    for(int j = 0 ; j < m ; ++j )
                       {
                            if(x[i][j] != '#')
                            {
                       int node1 = i*m+(j+1);
                       if(x[i][j]=='C')
                         choc.push_back(node1);
                         else
                         if(x[i][j]=='T')
                          source = node1;
                          else
                          if(x[i][j] =='W')
                          dest = node1;
                                if(i+1 < n )
                                {
                                    int node2 = (i+1)*m+(j+1);
                                    graph[node1].push_back(node2);
                                    graph[node2].push_back(node1);
                                }
                                if(j+1<m)
                                {
                                 int node2 = i*m + (j+2);
                                    graph[node1].push_back(node2);
                                    graph[node2].push_back(node1);
                                }
                        }
                    }
                 }
                 int arr[12][12]={0};
                  int dist[10001];
                  int visit[10001];
                   for(int i = 0 ; i <= 10000 ; ++i ){
                      dist[i] = 1e9;
                      visit[i] = 0;
                   }
                     queue<int> q;
                     q.push(source);
                      dist[source] = 0 ;
                      while(!q.empty())
                      {
                          int u  = q.front();
                           q.pop();
                          if(visit[u] == 1)
                           continue;
                          for(int i = 0 ; i < graph[u].size() ; ++i )
                          {
                              int v = graph[u][i];
                              if(visit[v] == 0)
                              {
                                   if(dist[v] == 0)
                                  dist[v] = dist[u] + 1;
                                  else
                                  dist[v] = min(dist[v] , dist[u]+1);
                                   q.push(v);
                              }

                          }
                          visit[u] = 1;
                      }
                    for(int i = 0 ; i < choc.size() ; ++i )
                    {
                        arr[1][i+2] = dist[choc[i]];
                    }
                    arr[1][choc.size()+2] = dist[dest];
                    arr[choc.size()+2][1] = dist[dest];
                    for(int j = 0 ; j < choc.size() ; ++j )
                    {
                        for(int i = 0 ; i <= 10000 ; ++i )
                         {
                              dist[i] = 1e9;
                              visit[i] = 0;
                            }
                              q.push(choc[j]);
                      dist[choc[j]] = 0 ;
                      while(!q.empty())
                      {
                          int u  = q.front();
                           q.pop();
                          if(visit[u] == 1)
                           continue;
                          for(int i = 0 ; i < graph[u].size() ; ++i )
                          {
                              int v = graph[u][i];
                              if(visit[v] == 0)
                              {
                                  dist[v] = dist[u] + 1;
                                   q.push(v);
                              }

                          }
                          visit[u] = 1;
                      }
                      arr[j+2][1] = dist[source];
                      arr[j+2][choc.size()+2]= dist[dest];
                      arr[choc.size()+2][j+2]= dist[dest];
                     for(int i = 0 ; i < choc.size() ; ++i )
                         arr[j+2][i+2] = dist[choc[i]];
                      }
                      int size = choc.size()+2;
                      int flag = 0;
                      for(int i = 1 ; i <= size ; ++i )
                      {
                           for(int j = 1 ; j <= size ; ++j )
                               if(arr[i][j] == 1e9)
                                 flag = 1;
                      }
                          if(flag == 1)
                     cout <<"Mission Failed!"<<endl;
                     else{
                         ans = 1e9;
                         int vis[13]={0};
                           vis[1] = 1;
                        cst(arr,1,size,size ,0,vis,1);
                        cout << ans << endl;
                     }

           }
           return 0;
}

SPOJ -> ABCD - Colours A, B, C, D

#include<bits/stdc++.h>
using namespace std;
int main(){

       int  n;
       cin >> n;
       string x;

        cin >> x;
        string ans;

          for(int i = 0 ; i < 2*n ; i=i+2)
           {
                 int p1=-1;
                 int p2=-1;
                 int b[4]={1,1,1,1};
                 b[x[i]-'A']=0;
                 b[x[i+1]-'A']=0;
                 for(int j = 0 ; j < 4 ; ++j )
                 {
                     if(b[j]==1)
                     {
                         if(p1 == -1)
                         p1 = j;
                         else
                         p2 = j;
                     }


                 }
                  ans+=(p1+'A');
                  ans+=(p2+'A');
                  if(ans[i] == ans[i-1])
                   swap(ans[i],ans[i+1]);
           }
            cout << ans << endl;

    return 0;
          }

SPOJ -> POWERUP - Power the Power Up

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long fast(long long base , long long exp , long long mod)
{
   long long res = 1;
     while(exp){
       if(exp&1)
        res = (res%mod * base%mod) % mod;
        exp = exp >> 1;
        base = (base%mod * base%mod) % mod;
        }
        return res;

}
int main(){

                   while(true){

                       long long a , b , c;
                        cin >> a >> b >> c;
                        if(a == -1 &&  b == -1 && c == -1)
                             break;
                         if(c == 0)
                          cout << (a%MOD) <<endl;
                          else
                         if(b == 0)
                          cout <<"1" << endl;
                          else
                          if(a%MOD == 0)
                          cout <<"0"<<endl;
                          else {
                        long long result2 = fast( b , c , MOD-1);
                        long long result1 = fast(a , result2 , MOD);
                        cout << result1 << endl;
                      }
                   }
                   return 0;
}

SPOJ -> SUMPRO - SUM OF PRODUCT

#include<bits/stdc++.h>
#define  mod 1000000007
using namespace std;
int main(){

      int t;
      cin >> t;
      while(t--){

               long long  n , i ;
               cin >> n;
             long long ans = 0;
             long long last;
                 for( i = 1; i*i <= n ; ++i )
                       ans = (ans + (i * (n/i))%mod)%mod;
                     --i;
                     last = n/i;
                    for( i = 1; i < last ; ++i )
                    {
                        long long en = n/i;
                        long long st = n/(i+1);
                            long long diff = (en*(en+1)/2 )-  (st*(st+1)/2);
                              ans =  (ans + (i*diff)%mod)%mod;

                    }

                 cout << ans << endl;
      }

        return 0;

 }

Properties of modulus operator

Properties of modulus operator

(a+b)%m=(a%m+b%m)%m

(a*b)%m=(a%m+b%m)%m

modulus of a (negative) number

 (a%b+b)%b
     where a<0


NOTE: modulus operator gave wrong values in case of division


 example=(a/b)%m is not calculate directly
 
  (a/b)%m=  (a%m*inverse(b)%m)%m

  where inverse of b=b^(m-2)%m  
 
here m is a prime number.

Summation and series

Successive difference formulae for the series having constant kth successive difference

           

           

=

                    

SUMMATION FORMULAE

   

Number of bst

Number of binary search tree having n vertices


   (2n)!/(n!*(n+1)!)
   which is equals to the nth CATALAN number
    CATALAN  series
    1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,                 35357670, 129644790,477638700, 1767263190, 6564120420, 24466267020, 91482563640,               343059613650, 1289904147324, 4861946401452..........

    Recurrence relation for catalan series..

   c(0)=1;
   c(n+1)=sigma(c(i)*c(n-i)) over i=0 to n.

calculate nCr%m

How to calculate nCr mod m when m is a prime number
      ncr=n!/r!(n-r)!
      (n!%m*inverse(r!)%m*inverse((n-r)!)%m)%m

      fact[i]=i*fact[i-1]%m
      inverse[i]=fact[i]^(m-2)%m
      by fermets' little theorm
      inverse(b)%m=b^(m-2)%m
      and we can calculate power of any number using fast exponentiation
      to avoid the time limitation.
      as we are using arrays to save our results it is good enough (n<=10000000)

   If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then    use Chinese Remainder Theorem(CRT) to find nCr mod m.
 
 also, we can calculate nCr for any m which is small enough (say m ≤ 5000) or small n and r (say r ≤ n ≤ 5000)    by using the following recursion with memoization having time complexity O(n*r)
         nCr = n-1Cr + n-1Cr-1

Counting the number of leading zeros in n!

Counting the number of leading zeros in n!

     from one combination of 2 and 5 we can get one zero,so we have to count the total

     number of pairs of 2 and 5 in n! .

     exponent of p in n!

     floor(n/p)+floor(n/p^2)+floor(n/p^3).......

     example-  n=10

     exponent of 2  in 10!=(10/2)+(10/4)+(10/8)+(10/16)....

     =5+2+1+0+0...   = 8

     exponent of  5 in 10!=(10/5)+(10/25).......

     =2+0+0....=2

     total combination of (2,5)=min(2,8)

    total number of leading zeros in 10!=2

    10!=3628800.

 Counting the number of digits in n!

     log(n!)=log(1)+log(2)+log(3)........log(n).

Counting the number of leading zeros of  n! in base b

    factorise b=p1^e1*p2^e2*p3^e3......   where p1,p2,p3.. are prime and e1,e2,e3.. are their exponent

    then calculate exponent of  each prime in n!  divided by their exponent and the number of leading       zeros of n! in base b  is

        min(1/e1((n/p1)+(n/p1^2)....),1/e2((n/p2)+(n/p2^2)....),1/e3((n/p3)+(n/p3^2)....).....)

   

Counting the number of digits of n! in base b

   log(n!)/log(b)+1