Uva 10288 – Coupons

Category : DP, PIE, Probability
Solution:
First I will discuss DP solution.
Let f(x) = # of expected move to achieve x different coupons.
We know already f(0), f(1)…. ,f(x-1);
Now To achieve x different moves, Lets consider a coupon. We have two case

The coupons is one of the x-1 of f(x-1)

This could be different from the x-1 of f(x-1)

This lead us to a dp solution .

This leads us to a closed form

code :

//
//  main.cpp
//  10288 - Coupons
//
//  Created by Repon Macbook on 12/28/15.
//  Copyright © 2015 Repon Macbook. All rights reserved.
//

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < (n) ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}


int len(Long n)
{
      int cnt = 0;
      while(n){
            cnt ++;
            n/=10;
      }
      return cnt;
}
class Frac {
public:
      long long a, b;
      Frac() {
            a = 0, b = 1;
      }
      Frac(long long x, long long y) {
            a = x, b = y;
            reduce();
      }
      Frac operator+(const Frac &y) {
            long long ta, tb;
            tb = this->b/gcd(this->b, y.b)*y.b;
            ta = this->a*(tb/this->b) + y.a*(tb/y.b);
            Frac z(ta, tb);
            return z;
      }
      Frac operator-(const Frac &y) {
            long long ta, tb;
            tb = this->b/gcd(this->b, y.b)*y.b;
            ta = this->a*(tb/this->b) - y.a*(tb/y.b);
            Frac z(ta, tb);
            return z;
      }
      Frac operator*(const Frac &y) {
            long long tx, ty, tz, tw, g;
            tx = this->a, ty = y.b;
            g = gcd(tx, ty), tx /= g, ty /= g;
            tz = this->b, tw = y.a;
            g = gcd(tz, tw), tz /= g, tw /= g;
            Frac z(tx*tw, ty*tz);
            return z;
      }
      Frac operator/(const Frac &y) {
            long long tx, ty, tz, tw, g;
            tx = this->a, ty = y.a;
            g = gcd(tx, ty), tx /= g, ty /= g;
            tz = this->b, tw = y.b;
            g = gcd(tz, tw), tz /= g, tw /= g;
            Frac z(tx*tw, ty*tz);
            return z;
      }
      void print()
      {
            if(b==1) {
                  printf("%lld\n", a);
            }else {
                  Long o = a/b;
                  Long d = a%b;
                  int pad = len(o);
                  int dag = len(b);
                  if(o) {
                        forn(i,pad+1) printf(" ");
                        printf("%lld\n", d);
                        printf("%lld ",o);
                        forn(i,dag) printf("-");
                        printf("\n");
                        forn(i,pad+1) printf(" ");
                        printf("%lld\n",b);
                  }else {
                        printf("%lld\n",d);
                        forn(i,dag) printf(" ");
                        printf("%lld\n",b);
                        
                  }
            }
      }
private:
      static long long gcd(long long x, long long y) {
            if(!y)  return x;
            if(x < 0)   x *= -1;
            if(y < 0)   y *= -1;
            long long t;
            while(x%y)
                  t = x, x = y, y = t%y;
            return y;
      }
      void reduce() {
            long long g = gcd(a, b);
            a /= g, b /= g;
            if(b < 0)   a *= -1, b *= -1;
      }
};
/*************************** END OF TEMPLATE ****************************/
const int N = 1001;
int n;



int main()
{
      
      
      Frac ans;
      while(scanf("%d",&n)==1) {
            ans = {0,1};
            
            
            for(int i= 1;i <=n; i ++ ) {
                  ans = ans + Frac(n,n-i+1);
            }
            ans.print();
      }
      return 0;
}

Another solution is using Principal of Inclusion-Exclusion.
The formula is :

Using this is really easy.
code :

//
//  main.cpp
//  10288 - Coupons
//
//  Created by Repon Macbook on 12/28/15.
//  Copyright © 2015 Repon Macbook. All rights reserved.
//

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < (n) ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}


int len(Long n)
{
      int cnt = 0;
      while(n){
            cnt ++;
            n/=10;
      }
      return cnt;
}
class Frac {
public:
      long long a, b;
      Frac() {
            a = 0, b = 1;
      }
      Frac(long long x, long long y) {
            a = x, b = y;
            reduce();
      }
      Frac operator+(const Frac &y) {
            long long ta, tb;
            tb = this->b/gcd(this->b, y.b)*y.b;
            ta = this->a*(tb/this->b) + y.a*(tb/y.b);
            Frac z(ta, tb);
            return z;
      }
      Frac operator-(const Frac &y) {
            long long ta, tb;
            tb = this->b/gcd(this->b, y.b)*y.b;
            ta = this->a*(tb/this->b) - y.a*(tb/y.b);
            Frac z(ta, tb);
            return z;
      }
      Frac operator*(const Frac &y) {
            long long tx, ty, tz, tw, g;
            tx = this->a, ty = y.b;
            g = gcd(tx, ty), tx /= g, ty /= g;
            tz = this->b, tw = y.a;
            g = gcd(tz, tw), tz /= g, tw /= g;
            Frac z(tx*tw, ty*tz);
            return z;
      }
      Frac operator/(const Frac &y) {
            long long tx, ty, tz, tw, g;
            tx = this->a, ty = y.a;
            g = gcd(tx, ty), tx /= g, ty /= g;
            tz = this->b, tw = y.b;
            g = gcd(tz, tw), tz /= g, tw /= g;
            Frac z(tx*tw, ty*tz);
            return z;
      }
      void print()
      {
            if(b==1) {
                  printf("%lld\n", a);
            }else {
                  Long o = a/b;
                  Long d = a%b;
                  int pad = len(o);
                  int dag = len(b);
                  if(o) {
                        forn(i,pad+1) printf(" ");
                        printf("%lld\n", d);
                        printf("%lld ",o);
                        forn(i,dag) printf("-");
                        printf("\n");
                        forn(i,pad+1) printf(" ");
                        printf("%lld\n",b);
                  }else {
                        printf("%lld\n",d);
                        forn(i,dag) printf(" ");
                        printf("%lld\n",b);
                        
                  }
            }
      }
private:
      static long long gcd(long long x, long long y) {
            if(!y)  return x;
            if(x < 0)   x *= -1;
            if(y < 0)   y *= -1;
            long long t;
            while(x%y)
                  t = x, x = y, y = t%y;
            return y;
      }
      void reduce() {
            long long g = gcd(a, b);
            a /= g, b /= g;
            if(b < 0)   a *= -1, b *= -1;
      }
};
/*************************** END OF TEMPLATE ****************************/
const int N = 1001;
int n;

Long comb[40][40];

void f()
{
      for(int i = 0; i < 34; i ++ ) {
            comb[i][0] = 1;
            for(int j = 1;j <=i; j ++ ) {
                  comb[i][j]=  comb[i-1][j] + comb[i-1][j-1];
            }
      }
}


int main()
{
      
      f();
      Frac ans;
      while(scanf("%d",&n)==1) {
            ans = {0,1};
            for(int i = 1;i <= n; i ++ ) {
                  if(i&1)ans = ans + Frac(n*comb[n][i], i);
                  else ans =ans- Frac(n*comb[n][i], i);
            }
            
            
            ans.print();
      }
      return 0;
}

LightOJ – 1124 – Cricket Ranking

Category : PIE
Solution :
If We are not given any bound, then,

How many Integer solution of this equation ?

This is Simply

If We are given only the lower bound of this variables, Such as x1>= p1, x2>=p2, x3>=p3, How can We find the solution ?

Simple: Replace x1 = p1 + y1, x2 = p2 + y2, x3 = p3 + y3,

Now We get from equation (1) :

Equation 2 has no constraint, No lower_bound, In this way we can handle lower_bound

Now The later section handles the upper bound constraint.

This image is taken from a book. This Book illustrates the generalised PIE to solve this problem.
The GPIE is States bellow:

From This principal We can State The following

Now See the discussion :

Now My Code :

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
template <class T> inline T bigmod(T p,T e,T M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const Long MOD = 100000007;
const int N = 1e6+20;
Long fa[N];
void f()
{
      fa[0] = 1;
      for(int i=1;i<N;i++) fa[i] = i*fa[i-1], fa[i] %= MOD;
      //for(int i=1;i<N;i++) rfa[i] = modinverse(fa[i], (Long)MOD);
      
}
Long calc(Long n,Long r)
{
      Long c = fa[n];
      Long d = (fa[r] * fa[n-r]) % MOD;
      return c * (modinverse(d,(Long) MOD)) % MOD;
}
int ar[11];
int main()
{
      f();
      Di(t);
      int cs = 0;
      while(t--) {
            Dii(k,n);
            Long sum = 0;
            forn(i,k) {
                  Dii(a,b); if(a>b)swap(a,b);
                  ar[i] = b - a+1 ;
                  sum += a;
            }
            Long dk = n - sum;
            if(dk < 0 ) {
                  printf("Case %d: 0\n",++cs);
                  continue;
            }
            
            Long ans = 0;
            
            forn(i, 1 << k ) {
                  Long uu = 0;
                  int cnt= 0;
                  for(int j = 0; j < k; j ++ ) {
                        if(i&1<<j) {
                              cnt ++;
                              uu += ar[j];
                        }
                  }
                  Long p = dk - uu + k -1;
                  Long q = k-1;
                  if(p <q ) continue;
                  ans += calc(p,q) * (cnt&1 ? -1: 1);
                  ans %= MOD;
            }
            printf("Case %d: %lld\n" , ++cs, (ans + MOD) % MOD);
            
      }
}

CF 547C

Problem Link : 547C
Discussion : This problem uses PIE,
For details please see this Link

Here is my implementation:

/*
 
 *************************
 Id  : Matrix.code
 Task: 547C
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 5e5+5;
int a[N];
vector<int>f[N];
bool inq[N];
int d[N];
bool vis[N];

void seive()
{
      for(int i= 2; i < N; i ++ ) {
            if(vis[i]) continue;
            f[i].pb(i);
            for(int j = 2 * i ; j <N ; j += i ) {
                  f[j].pb(i);
                  vis[j]=1;
            }
      }
}

int size = 0;
int main()
{
      seive();
      Dii(n,q);
      for(int i = 1;i <= n; i ++ ) Si(a[i]);
      Long ans = 0;
      while(q--){
            Di(in);
            if(inq[in] == 0){
                  
                  inq[in] =1;
                  int SZ = f[a[in]].Sz;
                  Long t = 0;
                  for(int i= 1; i < 1<<SZ ; i ++ ) {
                        int p = 1,cnt=0;
                        for(int j = 0; j < SZ; j ++ ) {
                              if(i&1<<j) {
                                    p *= f[a[in]][j];
                                    cnt ++;
                              }
                        }
                        t += (cnt&1 ? 1 : -1 ) * d[p];
                        d[p] ++;
                        
                  }
                  ans+= size - t;
                  printf("%lld\n", ans);
                  size ++;
            }
            else {
                  size --;
                  inq[in] = 0;
                  int SZ = f[a[in]].Sz;
                  Long t = 0;
                  for(int i= 1;i <1<<SZ; i ++ ){
                        int p=1,cnt = 0;
                        for(int j= 0;j < SZ; j ++ ){
                              if(i&1<<j) {
                                    p *= f[a[in]][j];
                                    cnt ++;
                              }
                        }
                        d[p]--;
                        t += (cnt &1 ? 1:-1) * d[p];
                        
                  }
                  ans -= size - t;
                  printf("%lld\n", ans);
                  
            }
      }
      
      return 0;
}

HDU – 4135 – Co-Prime

Category : PIE
Problem Link : HDU – 4135
Discussion:
Given a,b,n. How many integer in range [a,b] are co-prime to number n. (a,b <= 10^15, and n <= 10^9)
Solution:

Enumerate all the prime factor of n.

Now we can apply to PIE to find the number of integer in range [1,x] which is divisible by at least one of the prime factor of n. Hence not co-prime to n.

Lastly , The answer f(b) – f(a-1)

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 1e5+5;
bool vis[N];
vector<Long> F,Prime;
Long a,b,n;


void seive()
{
      int sqn = sqrt(1e9+1);
      for(int i  = 2; i < sqn; i ++ ) {
            if(vis[i] == 0 ){
                  Prime.pb(i);
                  for(int j= 2 * i; j < sqn ; j += i) vis[j] = 1;
            }
      }
}
void fact(Long n)
{
      for(int i =0 ; i < Prime.Sz && Prime[i] * Prime[i] <= n;i ++ ) if(n%Prime[i] == 0){
            while(n%Prime[i] == 0) n/=Prime[i];
            F.pb(Prime[i]);
      }
      if(n>1)F.pb(n);
}

Long ans= 0;
void dfs(Long M,int ind, int flag, Long num)
{
      if(M > num )return;
      if(ind == F.Sz){
            if(M!=1) {
                  ans += num/M *flag;
                  //db(ans);
            }
            return;
      }
      dfs(M * F[ind] , ind+1, -flag, num);
      dfs(M , ind+1, flag, num );
}


Long solve(Long a)
{
      ans = 0;
      dfs(1,0,-1,a);
      //db(ans);
      return a - ans;
}
int main()
{
      seive();
      Di(t);
      int cs = 0;
      while(t--) {
            cin >> a >> b >> n;
            fact(n);
            //db(F.Sz);
            printf("Case #%d: %lld\n", ++cs , solve(b)- solve(a-1));
            F.clear();
      }
      
      return 0;
}

Another problem using the same concept :
Link : HDU – 2841
Discussion:
Given n,m. Need to find how many unique a/b pair where 1<=a <= n , and 1 <= b <= m;
Solution:

Like the previous solution, for each i in range [1,n] , We need to find how many co-primes in range[1,m] which is co-prime to i

Iterate all the i, add them to sum

/*
 
 *************************
 Id  : Matrix.code
 Task: HDU - 2841
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 1e5+5;
vector<int> Prime;
vector<int> F[N];
bool vis[N];
void seive()
{
      for(int i= 2;i < N; i ++ ) {
            if(vis[i]) continue;
            Prime.pb(i);
            F[i].pb(i);
            for(int j = 2 * i; j < N; j +=i ){
                  F[j] .pb(i);
                  vis[j] = 1;
            }
      }
}
int divi;
Long ans;
void dfs(int M, int ind, int flag , int a)
{
      if(M > a) return;
      if(ind == F[divi].Sz) {
            if(M>1) ans += a / M * flag;
            
            //db(ans);
            return;
      }
      dfs(M * F[divi][ind] , ind + 1, -flag, a);
      dfs(M , ind+1, flag , a);
}

Long solve(int a,int b)
{
      ans = 0;
      divi  = b;
      dfs(1,0,-1,a);
      //db(ans);
      return a-ans;
}

int main()
{
      seive();
      Di(t);
      while(t--) {
            Dii(n,m);
            Long ans = 0;
            for(int i = 1;i <= n; i ++ ) {
                  ans += solve(m,i);
            }
            printf("%lld\n", ans );
      }
      return 0;
}

PIE Continued->

Problem Link : HDU – 3208
Discussion:
This is another PIE problem. Now let’s see how to apply PIE.
consider integer in form = ,
This type of integer is counted in
So this is over counting.How to remove it ? Okay, Starting from the largest possible power,(2^60 >1e18) So largest power would be 59,

Lets denote cnt[i] = How many integer in range[1..n] which power(according to the problem definition) = i;
now for i = 12, We can calculate this numbers ,
But this numbers will also included in i=6,i=4,i=3,i=2,i=1, For all this divisors of 12, we need to subtract cnt[12], because this numbers has power = 12 , not 6,4,3,2,1

/*
 
 *************************
 Id  : Matrix.code
 Task: HDU - 3208
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 1001;
vector<int> Prime;
bool vis[60];

void seive()
{
      for(int i= 2;i < 60 ; i ++ ) {
            if(vis[i]==0) {
                  Prime.pb(i);
                  for(int j = 2 * i ; j < 60; j += i ) vis[j] = 1;
            }
      }
}


Long cnt[60];


Long get(Long a,int p)
{
      Long low =1  , high = pow(a,1./p) + 100 , mid , ans =1;
      while(low <= high) {
            mid = (low + high) / 2;
            
            double oo  = 1;
            Long k = 1;
            for(int i = 0; i < p ;i ++) {
                  oo *= mid;
                  k *= mid;
            }
            if(oo <= 2e18) {
                  if(k <= a) {
                        ans = mid;
                        low = mid+1;
                  }else high = mid-1;
            }
            else high = mid-1;
      }
      return ans;
}
Long solve(Long a)
{
      
      Long res = 0 ;
      ms(cnt,0);
      for(int i = 59 ; i >= 1; i-- ) {
            cnt[i] += get(a,i) - 1;
            for(int j = 1; j < i ; j ++ ) {
                  if( i % j == 0 ) {
                        cnt[j] -= cnt[i];
                  }
            }
            // if(cnt[i])printf("cnt[%d] -> %d\n" ,i, cnt[i]);
      }
      
      for(int i= 1; i<60; i ++ ) res += cnt[i] * i;
      return res;
}

int main()
{
      seive();
      Long a,b;
      while(scanf("%lld %lld",&a,&b)==2){
            if(a== 0 && b== 0 ) return 0;
            printf("%lld\n" , solve(b) - solve(a-1));
      }
      return 0;
}

Beware of ill -performance of pow function. I need to manually search then depending on pow function.

Principal of Inclusion-Exclusion

Problem Link : Problem 1
Simple Problem: One of the basic applications of Principal of Inclusion-Exclusion (PIE) .

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N= 16;
int a[N];

int main()
{
      Dii(n,k);
      forn(i,k) Si(a[i]);
      Long ans =0 ;
      forn(i,1<<k){
            Long p = 1, cnt = 0;
            forn(j,k) {
                  if(i&1<<j) {
                        cnt ++;
                        Long g = gcd(p,a[j]);
                        p = p * a[j] /g;
                  }
                  
            }
            if(cnt) {
                  if(cnt % 2) ans += n/p;
                  else ans -= n/p;
            }
        
      }
      printf("%lld\n", n - ans);
      return 0;
}

The time-complexity can slightly improved if we delete a number such that it has a divisor already in the list. With this We can shrink the size of the SET.

 
#include <bits/stdc++.h>
using namespace std;
 
/*------- Constants---- */
 
#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
 
/*************************** END OF TEMPLATE ****************************/
 
const int N = 1001;
bool vis[20];
int a[N];
 
int main()
{
      Dii(n,k);
      forn(i,k) Si(a[i]);
      sort(a,a+k);
      vector<int> I;
      forn(i,k) I.pb(a[i]);
      I.resize(unique(all(I)) - I.begin());
      
      for(int i = 0; i< I.Sz; i++ ) {
            for(int j = i+1 ; j < I.Sz; j ++) {
                  if(I[j] % I[i] == 0 ) vis[j] = 1;
            }
      }
      vector<int> S;
      for(int i = 0; i < I.Sz;i ++ ) {
            if(vis[i] == 0 )S.pb(I[i]);
      }
      Long ans= 0;
      forn(i,1<<S.Sz){
            Long p = 1, cnt = 0;
            double d = 1;
            forn(j,S.Sz) {
                  if(i&1<<j) {
                        cnt ++;
                        Long g = gcd(p,S[j]);
                        p = p * S[j] /g;
                        d = d * S[j] /g;
                  }
                  
            }
            if(cnt && d <= n + EPS) {
                  if(cnt % 2) ans += n/p;
                  else ans -= n/p;
            }
            
      }
      printf("%lld\n", n - ans);
      return 0;
} 

Problem 2 : HDU – 2204
Solution:
Maximum value of K = 60 , as 2^60> 1e18;
The number of primes <= 60 , 17
So, We need to calculate as follows, How many numbers is in form p^2, p^3,….

Now when calculating # of perfect square, and # of perfect cube , we overcount , some numbers are counted twice. What are they, Number in form p^6, as this number is in form (p^3)^2, and in form (p^2)^3, Thus the PIE apples.

So we need to subtract overcount .

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 60;
vector<int> Prime;
bool vis[N];

void seive()
{
      for(int i= 2;i < 60 ; i ++ ) {
            if(vis[i]==0) {
                  Prime.pb(i);
                  for(int j = 2 * i ; j < 60; j += i ) vis[j] = 1;
            }
      }
}


Long ans;
Long n;

void dfs(int M,  int ind , int p)
{
      if(M >60 || (1LL << M ) > n) return;
      if(ind == Prime.Sz) {
            if(M!=1) {
                  ans += ((int) (pow(n, 1./M) ) - 1)  * p;
            }
            return;
      }
      dfs(M * Prime[ind] , ind+1,-p);
      dfs(M , ind+1, p);
}
int main()
{
      seive();
      
      while(scanf("%lld",&n)==1) {
            ans=1;
            dfs(1,0,-1);
            
            printf("%lld\n", ans);
      }
      return 0;
}

Again This code can be re-written by using bit mask technique

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 60;
vector<int> Prime;
bool vis[N];

void seive()
{
      for(int i= 2;i < 60 ; i ++ ) {
            if(vis[i]==0) {
                  Prime.pb(i);
                  for(int j = 2 * i ; j < 60; j += i ) vis[j] = 1;
            }
      }
}


Long ans;
Long n;

int main()
{
      seive();
      
      while(scanf("%lld",&n)==1) {
            ans=1;
            for(int i  = 1;i < 1<< Prime.Sz; i ++) {
                  int k = 1 , cnt = 0;
                  bool flag = 1;
                  for(int j = 0; j < Prime.Sz; j ++ ) {
                        if( i & 1<< j  )
                        {
                              k *= Prime[j];
                              if( k > 60 ) {
                                    flag=  0;
                              }
                              cnt ++;
                        }
                  }
                  if(flag) {
                        ans += ((int) (pow(n,1./k) + EPS )-1) * ((cnt&1) ? 1 : -1);
                        //db(ans);
                  }
            }
            
            
            
            printf("%lld\n", ans);
      }
      return 0;
}

SQRT – DECOMPOSITION

Problem : CF – 455D

/*
 
 *************************
 Id  : Matrix.code
 Task: 455D
 Date: 
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < (n) ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 1e5+5;
const int SZ=320;
int a[N];
int low[SZ], high[SZ] , num[N], cnt[SZ][100101];
deque<int> q[SZ];


void update(int x,int y)
{
      int b = num[y];
      int index = y - low[b];
      int v = q[b][index];
      q[b].erase(q[b].begin() + index);
      cnt[b][v] --;
      for( --b; b>= num[x];  b--) {
            int back = q[b].back();
            q[b].pop_back();
            cnt[b][back] --;
            q[b+1].push_front(back);
            cnt[b+1][back] ++;
      }
      b ++;
      q[b].insert(q[b].begin() + (x-low[b]), v );
      cnt[b][v] ++;
}

int query(int x,int y,int k)
{
      if(num[x] == num[y]) {
            int res = 0;
            int b = num[x];
            int p = x - low[b] , p2 = y - low[b];
            
            for(int i = p; i <= p2; i ++ ) {
                  if(q[b][i] == k) {
                        res ++;
                  }
            }
            return res;
      }
      int b = num[x] , res = 0;
      for(int i = x; num[i] == num[x] ; i ++) {
            if(q[b][i - low[b]]== k) {
                  res ++;
            }
      }
      for(int i = num[x] + 1; i < num[y] ; i ++ ) {
            res += cnt[i][k];
      }
      b = num[y];
      for(int i = y; num[y] == num[i]  ; i--) {
            res += q[b][i - low[b]] == k;
      }
      return res;
}

int main()
{
      
      Di(n);
      for(int i = 1;i <= n; i ++ ) Si(a[i]);
      int sq = sqrt(n) + EPS , cn = 0,col = 0;
      low[0] =1;
      for(int i = 1; i <=n ;i ++ ) {
            cn ++;
            if(cn > sq) {
                  cn = 0;
                  col ++;
                  low[col] = i;
            }
            num[i] = col;
            high[ num[i]] = i;
            q[num[i]].push_back(a[i]);
            cnt[ num[i]][a[i]] ++;
      }
      
      
      
      Di(q);
      int z = 0;
      while(q--  ) {
            Di(t);
            if(t==1) {
                  Dii(x,y);
                  x = (x + z-1) %n + 1;
                  y = (y + z-1) %n + 1;
                  if(x>y)swap(x,y);
                  update(x,y);
            }
            else {
                  Diii(x,y,k);
                  x = (x+z-1)%n+1;
                  y = (y+z-1)%n+1;
                  k = (k+z-1)%n+1;
                  if(x>y)swap(x,y);
                  z=query(x,y,k);
                  printf("%d\n",z);
                  
            }
      }
      return 0;
}

Digit DP HDU – 4352

Link : 4352

Solution:

This is a digit dp problem,The only problem is how to store lis information and use it to calculate same result more than twice.
Now LIS is a well known topic. There is a n log(n) solution for LIS. The technique used to find LIS, is needed here . Compactly store info about LIS.

Now Let’s see, we are given a sequence [2,5,3,4], We can see LIS = 3 [2,3,4]
How do we compute this result ?

vector<int>I;
for(int i = 0 ; i < ar.size(); i ++ )
// find a position where I can put ar[i].Let it is Pos , such that I[Pos+1] >= ar[i]
if(Pos>=I.size()) {
I.push_back(a[i]);
}else I[pos] = ar[i];
}
LIS = I.size();

For more detail ,please see the link : LIS

How it will look,
After entering 2, I = {2}
After entering 5, I = {2,5}
After entering 5, I = {2,3} // Note here we have replaced 5 with 3
After entering 4, I = {2,3,4}
So, LIS = 3,

The same think is needed ,but difference is,We need to store them using bit mask.

Let S is Bitmask represent LIS ;
Now lets see how to co-operate S with I giving the same result at the end

After entering 2, I = {2} , S = 000010
After entering 5, I = {2,5}, S = 100010
After entering 5, I = {2,3}, S = 000110, We make the first bit which is 1 to zero greater than the input value
After entering 4, I = {2,3,4},S= 001110,
LIS = Number of set bits is S ( 3)

using this modification we can code digit dp easily

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < (n) ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 1001;

Long dp[20][1<<10][11];
int ar[20];
int nxt[1<<10][10];

Long F(int ind , int Mask, int k, bool flag)
{
      if(ind < 0 ) {
            if(__builtin_popcount(Mask) == k) return 1;
            return 0;
      }
      if(!flag && dp[ind][Mask][k] !=-1) return dp[ind][Mask][k];
      
      Long res = 0, Lim = flag ? ar[ind] : 9;
      for(int i = 0; i <= Lim ; i ++ ) {
            res += F(ind-1, nxt[Mask][i] , k , flag && i == Lim) ;
      }
      if(flag) return res;
      return dp[ind][Mask][k]  = res;
      
}



Long solve(Long a,int k)
{
      int ind = 0;
      for(ind = 0; a; ind ++ , a/=10) ar[ind] = a%10;
      return F(ind-1, 0,k,true);
}

int foo(int Mask,int digit)
{
      if(Mask == 0 && digit == 0) return 0;
      for(int i= digit ; i < 10 ;i ++ ) {
            if( Mask & (1<<i)){
                  Mask ^= 1<<i;
                  Mask ^= 1<<digit;
                  return Mask;
            }
      }
      return Mask ^= 1<<digit;
}
void work()
{
      for(int i = 0; i < 1<<10; i++ )
      {
            for(int j = 0;j < 10; j ++) {
                  nxt[i][j] = foo(i,j);
            }
      }
}

int main()
{
      ms(dp,-1);
      work();
      Long L,R;
      int k;
      Di(t);
      int cs = 0 ;
      while(t--) {
            
            Sii(L,R);
            Si(k);
            printf("Case #%d: %lld\n", ++cs, solve(R,k)  - solve(L-1,k));
      }
      
      
      return 0;
}

Uva 10934 – Dropping water balloons

Category : DP
Discussion:
This problem is similar to another problems unless its constraints are high (2^63-1).
If the limit of n was small , we could do dynamic programming to find the answer. Let’s see what it looks like.

// Here f(k,L,R) -> the minimum number of moves needed to ensure the required height in range[L,R] having k balloons left.

int f(int k,int L,int R)
{
     
      if(L>=R)return 0;
      if(k==1)return R-L+1;
      if(dp[k][L][R] !=-1) return dp[k][L][R];
      int res = INF;
      for(int i = L; i<R; i++) {
            res = min(res, 1 + max(f(k-1 , L,i-1) , f(k,i+1, R)));
      }

      return dp[k][L][R] =res;
}

Now think other side.

Let’s assume, for a fixed k, we know that, for n = 100, we need 10 moves. now can we claim that for n= 1 to 99, the answer <=10
That is for a fixed k ,the height we can assure is monotonous increasing function of moves number. So if we determine, For a fixed k and what is the maximum height we can assure using m moves. Then iterate through the moves.

dp(i,j) The maximum height possible to assure if I have i ballons left and j moves are left

Base case :
if(j==1) return 1; // If I have 1 move left, the maximum possible height to ensure is 1
if(i==1)return j; // Only 1 balloon left, so starting from 1,2,… to j th height we can experiment, as we have j moves.

Transition:

dp(i,j) = dp(i-1,j-1) + 1 + dp(i,j-1); I will choose The height H = dp(i-1,j-1)+ 1, drop a ballon from this height.

Let’s say, The balloons minimum cap = k;
if( k > H ) I need to do the experiment again. But I have 1 move low, This result correspond to dp(i,j-1)

See code:

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 101;

typedef unsigned long long u;

u dp[N][64]; // dp(i,j) The maximum height possible to assure if I have i ballons left and j moves are left
bool vis[N][N];
u f(int i,int j)
{
      if(j==1) return 1;
      if(i==1)return j;
      if(vis[i][j]) return dp[i][j];
      else dp[i][j] = 1 + f(i-1, j-1) + f(i,j-1);
      vis[i][j]= 1;
      return dp[i][j];
}


int main()
{
      
  
      u N;
      int k;
      while(scanf("%d %llu",&k,&N)==2) {
            if(!k)break;
            int ans= -1;
            bool flag = 0;
            for(int i = 1; i<= 63; i ++ ) {
                  if(f(k,i) >= N) {
                        flag = 1;
                        ans = i;
                        break;
                  }
            }
            if(flag) printf("%d\n",ans);
            else printf("More than 63 trials needed.\n");
      }
      return 0;
}

DP with profile

Problem Link : Link
Category: DP + Profile
Here Profile consist of two rows, Denote them Mask1,Mask2, current index,
DP states are F(Mask1, Mask2,int index)
In each stage we select such bit string that, this ensures Mask1 to be set all 1

//
//  main.cpp
//  1092 - Lighted Panels
//
//  Created by Repon Macbook on 12/11/15.
//  Copyright © 2015 MAC. All rights reserved.
/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 10;
char g[N][N];
int ar[N];
int r,c;
int dp[1<<8][1<<8][10];
int bits[1<<8];
vector<int> G[1<<8];
int oo[1<<8];
bool solve;

int F(int Mask1,int Mask2, int ind)
{
      if(ind == r) {
            if(Mask1== (1<<c)-1) {
                  solve = 1;
                  return 0;
            }
            return 1e8;
      }
      if(dp[Mask1][Mask2][ind] !=-1) return dp[Mask1][Mask2][ind];
      int res = 1e8;
      for(int j= 0; j < G[Mask1].Sz; j ++ ){
            int k = G[Mask1][j];// We store all the Mask that can Make Mask1 to set all 1,
            res = min(res , bits[k] + F(Mask2^oo[k] ,ar[ind+1] ^oo[k] , ind+1));
      }
      return dp[Mask1][Mask2][ind] = res;
      
}


int main()
{
      
      Di(t);
      int cs = 0;
      while(t--) {
            Sii(r,c);
            forn(i,r) scanf("%s",g[i]);
            forn(i,r) {
                  ar[i] = 0;
                  forn(j,c) if(g[i][j]=='*') ar[i] |= (1<<j);
            }
            forn(i,1<<c) {
                  forn(j,c) if(i&1<<j) bits[i] ++;
                  int prv = 0;
                  forn(j,c)if(i&1<<j){
                        prv ^=(1<<j);
                        if(j+1 < c )prv ^=(1<<(j+1));
                        if(j-1 >=0 ) prv ^= (1<<(j-1));
                  }
                  int M =( (1<<c)-1)  ^ prv;
                  G[M].pb(i);
                  oo[i] = prv;
                  
            }
            ms(dp,-1);
            int res = 1e8;
            solve=0;
            forn(i,1<<c) {
                  res = min(res , F(i,ar[0],0));
            }
            
            
            if(solve) {
                  printf("Case %d: %d\n",++cs, res );
            }else printf("Case %d: impossible\n",++cs);
            forn(i,1<<c) G[i].clear();
            ms(bits,0);
      }
      return 0;
}