Fast Multiplication

Category : FFT
Problem Link : HDU 1402

Solution :

/*
 *************************
 Id  : Matrix.code
 Task:
 Date: 2016-03-05

 **************************
 */


#include <bits/stdc++.h>
using namespace std;
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define Long                    long long
#define Ulong                   unsigned long long
#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 SZ(a)                   (int) a.size()
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define si(a)                   scanf("%d",&a);
#define sii(a,b)                si(a);si(b)
#define siii(a,b,c)             si(a);si(b);si(c)
#define sl(a)                   scanf("%lld",&a)
#define sll(a,b)                sl(a);sl(b)
#define slll(a,b,c)             sl(a);sll(b,c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define show(x)                 {for(auto ii: x) cout << ii <<" "; puts("");}
/*************************** END OF TEMPLATE ****************************/

typedef complex<double> Complex;
void fft(vector<Complex> & a, bool inv) {
	int n = (int)a.size();

	for (int i = 1, j = 0; i<n; ++i) {
		int bit = n >> 1;
		for (; j >= bit; bit >>= 1)
			j -= bit;
		j += bit;
		if (i < j)
			swap(a[i], a[j]);
	}

	for (int len = 2; len <= n; len <<= 1) {
		double ang = 2 * PI / len * (inv ? -1 : 1);
		Complex wlen(cos(ang), sin(ang));
		for (int i = 0; i<n; i += len) {
			Complex w(1);
			for (int j = 0; j<len / 2; ++j) {
				Complex u = a[i + j], v = a[i + j + len / 2] * w;
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
				w *= wlen;
			}
		}
	}
	if (inv)
	for (int i = 0; i<n; ++i)
		a[i] /= n;

}

vector<int> mult(vector<int>& a, vector<int>& b) {

	vector<Complex> fa(a.begin(), a.end()), fb(b.begin(), b.end());
	size_t n = 1;
	while (n < max(a.size(), b.size()))  n <<= 1;
	n <<= 1;
	fa.resize(n), fb.resize(n);

	fft(fa, false), fft(fb, false);
	for (size_t i = 0; i<n; ++i)
		fa[i] *= fb[i];
	fft(fa, true);

	vector<int> res;
	res.resize(n);
	for (size_t i = 0; i<n; ++i)
		res[i] = int(fa[i].real() + 0.5);
	return res;
}

const int N = 50005;

char a[N],b[N];
vector<int> A,B;
int main()
{
      while(scanf("%s %s",a,b)==2) {
            int lenA = strlen(a), lenB= strlen(b);
            A.clear();
            B.clear();
            for(int i= lenA-1; i>=0; i--) A.push_back(a[i]-'0');
            for(int i =lenB-1; i>=0 ;i--) B.push_back(b[i]-'0');
            vector<int> res= mult(A,B);
            int carry = 0;
            for(int i= 0;i < res.size();i ++) {
                  int k = res[i] + carry;
                  res[i] = k%10;
                  carry = k/10;
            }
            if(carry) res.pb(carry);

            bool flag = 0;
            for(int i = res.size()- 1; i>=0; i--) {
                  if(res[i])flag=1;
                  if(flag) printf("%d",res[i]);
            }
            if(!flag) printf("0");
            puts("");
      }
      return 0;
}

HDU – 3032

Category : Game Theory
Link : Problem

Solution :
The problem requires knowledge about nim game and Sprague–Grundy theorem. If you don’t know this, then game : topcoder
can help.

So proceed to solution, As each heap is independent, So this game is combination of games, and there we can apply grundy number.
We will find grundy number for each heap. If there are n heap, we calculate grundy number of each heap and xor them. If xorsum NONZERO, first one wins, othewise second person to move wins.

The only problem is to find grundy number of each pile.

Starting with 0 : grundy number gr(0) = 0, because it is a losing position.

When p = 1
we can move to only one position (0) , as 0 has grundy value of 0, then gr(1) = 1;

When p = 2
we can move to 0, 1, (1,1)(Spliting into 2 heap).

gr(2) = 2

When p = 3 we can move to 0, 1, 2,(1,2)(Spliting into 2 heap).

Here grundy value of the state (1,2) = 3 because gr(1) ^ gr(2) = 1 ^ 2 = 3;
so

gr(3) = 4

When p = 4

Here

gr(4) = 3

If we try like this we will find a pattern and this is

      if(n==0) return 0;
      if(n%4==1 || n%4 == 2) return n ;
      if(n%4 == 3) return n + 1;
      if(n%4 == 0) return n - 1;

So the solution is now obvious.

My code :

/*
 *************************
 Id  : Matrix.code
 Task: HDU - 3032
 Date: 2016-02-10

 **************************
 */


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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


/*------- 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 SZ(a)                   (int) a.size()
#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;

int gr(int n)
{
      if(n==0) return 0;
      if(n%4==1 || n%4 == 2) return n ;
      if(n%4 == 3) return n + 1;
      if(n%4 == 0) return n - 1;
}


int main()
{
      //freopen("in.txt","r",stdin);
      Di(t);
      while(t--) {
            Di(n);
            int ans = 0;
            for(int i = 0;i  < n; i ++ ) {
                  Di(a);
                  ans ^= gr(a);
            }
            printf("%s\n", ans ? "Alice" : "Bob");
      }
      return 0;

}

HDU – 4609 – 3-idiots

Category : FFT
Problem:
Given n(10^5) sticks.Picking 3 sticks from there. What is the probability so that it forms a triangle.

Solution:
Notations:

a[] -> The length of the sticks are stored
cnt[] -> cnt[i] denotes how many time length i occur

Let a[]= {1,2,3,3}
From this array picking two different integer, what length can we make?

1+2=3, 
1+3=4,
1+3=4
2+3=5, 
2+3=5,
3+3=6,

So We can represent them taking the occurance of the numbers. as follows

Table 1


0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
0 | 0 | 0 | 1 | 2 | 2 | 1 | 0 | 0

Now How to use FFT ?
Okay make polynomial of cnt[] array.
Thus,
$E = 2*x^3 + x^2 + x ;\\ E * E = E^2 = 4x^6 + 4x^5 + 5x^4 + 2x^3 +x^2$
The representation of this :

Table 2

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
0 | 0 | 1 | 2 | 5 | 4 | 4 | 0 | 0

You can guess how we find E^2, now can we find the prevous from this ?
{1,2,3,3} * {1,2,3,3}
By picking one from first and one from other,

1+1=2;
1+2=3;
1+3=4;
1+3=4;
2+1=3;
2+2=4;
2+3=5;
2+3=5;
3+1=4;
3+2=5;
3+3=6
3+3=6;
3+1=4;
3+2=5;
3+3=6
3+3=6;

So we represent this to array, it would look like the mentioned.
Now how to transform so that it generates table 1:
Note : For table 2,

a interger is adding to itself

1 + 2, 2+1, generates 2 but in table 1, it was generating 1, as permutation does not matter.

Using this above condition we can Transform 2 to Table 1
So, # minus num[a[i]*2] –, for every i
# divide each by 2 , num[i]/=2;

Now we have the Table 1 array.
How do we find the desired answer ?
sort the whole array,then take each length to be longest length of the triangle, So the summation of other sticks should be greater than this one.
details in code comment.

/*
 *************************
 Id  : Matrix.code
 Task: HDU - 4609
 Date: 2016-02-07

 **************************
 */


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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


/*------- 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 SZ(a)                   (int) a.size()
#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;}
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 = 1<<18;

typedef long double T;
long double PI = acos(-1.0); // Without long double gives WA
struct Complex{
      T x,y;
      Complex(T x=0,T y=0):x(x),y(y){}
      Complex operator + (const Complex &a) const{return Complex(x+a.x,y+a.y);};
      Complex operator - (const Complex &a) const{return Complex(x-a.x,y-a.y);};
      Complex operator * (const Complex &a) const{return Complex(x*a.x-y*a.y,x*a.y+y*a.x);};
};

struct Fast_Fourier{
      Complex A[1 << 18];
      int rev(int id, int len)
      { // Reversed bit value , 011 -> 110
            int ret = 0;
            for(int i = 0; (1 << i) < len; i++){
                  ret <<= 1;
                  if(id & (1 << i)) ret |= 1;
            }
            return ret;
      }


      void FFT(Complex a[], int len, int DFT)
      {
            for(int i = 0; i < len; i++) A[rev(i, len)] = a[i];
            for(int s = 1; (1 << s) <= len; s++)
            {
                  int m = (1 << s);
                  Complex wm = Complex(cos(DFT*2*PI/m), sin(DFT*2*PI/m));
                  for(int k = 0; k < len; k += m)
                  {
                        Complex w = Complex(1, 0);
                        for(int j = 0; j < (m >> 1); j++)
                        {
                              Complex t = w*A[k + j + (m >> 1)];
                              Complex u = A[k + j];
                              A[k + j] = u + t;
                              A[k + j + (m >> 1)] = u - t;
                              w = w*wm;
                        }
                  }
            }
            if(DFT == -1) for(int i = 0; i < len; i++) A[i].x /= len, A[i].y /= len;
            for(int i = 0; i < len; i++) a[i] = A[i];
            return;
      }

}fft ;
Complex x[1<<18];
Long num[1<<18];
int a[N];
int cnt[N];
Long sum[N];
int main()
{
     // freopen("in.txt","r",stdin);
      Di(t);
      while(t--) {
            Long n;
            Si(n);
            int iM = 0;
            for(int i= 0;i < n;i ++) {
                  Si(a[i]);
                  cnt[a[i]] ++;
                  iM = max(iM , a[i]);
            }
            sort(a,a+n);
            int len = 1;
            while(len <= 2 * iM) len *= 2;
            for(int i= 0;i < len;i ++) {
                  x[i] = Complex(cnt[i],0);
            }
            fft.FFT(x,len,1);
            for(int i= 0;i < len;i ++) {
                  x[i] = x[i] * x[i];
            }
            fft.FFT(x,len,-1);
            for(int i= 0;i < len;i ++) {
                  num[i] = (Long)(x[i].x + .5 );
            }
            for(int i= 0; i < n; i ++) {
                  num[a[i] + a[i]] --;
            }
            for(int i= 0;i < len;i ++) {
                  num[i]/=2;
            }
            // prefix sum
            for(int i= 1;i < len; i ++) {
                  sum[i] = num[i] + sum[i-1];
            }
            Long ans = 0;
            for(int i= 0 ;i < n; i++ ) {
                  ans += sum[len-1] - sum[a[i]]; // # of ways such that summation of length > a[i]
                  ans -= (n-1-i) * i; // as a[i], is the largest,so there are (n-1-i) are bigger than a[i]. They with any number less tham a[i] is included in first case. So substract them.
                  ans -= (n-1); 
                  ans -= (n-i-1) * (n-i-2) / 2; // number of ways where the both length > a[i] , subtract them.
            }
            Long tot = ((Long)n ) * (n-1) * (n-2)/6;
            printf("%.7lf\n", ans*1./ tot);
            ms(cnt,0);


      }
      return 0;

}

Xor-sequence

Problem Link : Xor – Sequence
Solution :

From the Hacker Rank editorial:
Let’s have a look at array A:

A1=1
A2=1⊕2
A3=1⊕2⊕3
A4=1⊕2⊕3⊕4
A5=1⊕2⊕3⊕4⊕5
…

Now, let’s make array B where Bi=A0⊕A1⊕A2⊕…⊕Ai.
Bi=A0⊕A1⊕A2⊕…⊕Ai−1⊕Ai=Bj⊕Aj+1⊕Aj+2⊕…⊕Ai. For any 0≤j<i.
So AL⊕AL+1⊕…⊕AR=BL−1⊕BR.

Now, let's have a look at array B:

B1=1
B2=2
B3=1⊕3
B4=2⊕4
B5=1⊕3⊕5
B6=2⊕4⊕6
B7=1⊕3⊕5⊕7
B8=2⊕4⊕6⊕8

It’s easy to observe that in odd indexes Bi=1⊕3⊕5⊕…⊕i
and for even indexes Bi=2⊕4⊕6⊕…⊕i

for even indexes there are numbers from 1 to i/2 multiplied by 2, that means bit’s are moved to left by 1, so, Bi=2⊕4⊕6⊕…⊕i=(1⊕2⊕3⊕…⊕i/2)∗2.
And for odd indexes there are numbers from 0 to (i−1)/2 multiplied by 2 and plus 1. That means bit’s are moved to left by 1, and last bit is made 1. so, Bi=1⊕3⊕5⊕…⊕i=(0⊕1⊕2⊕…⊕(i−1)/2)∗2+X.
X is 1⊕1⊕1⊕..⊕1 “ones” are repeated (i−1)/2+1 times. So, if (i−1)/2+1 is odd then X=1 else X=0.

Now, calculation of 1⊕2⊕3⊕…⊕x.
Let’s prove that (4K)⊕(4K+1)⊕(4K+2)⊕(4K+3)=0 for 0≤K.

My code:

/*
 *************************
 Id  : Matrix.code
 Task: Xor-sequence
 Date: 2016-02-01

 **************************
 */


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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


/*------- 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 SZ(a)                   (int) a.size()
#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 xo(Long t)
{
      if(t%4==0) return t;
      if(t%4==1) return 1;
      if(t%4==2) return t+1;
      if(t%4==3) return 0;
      return 0;
}

Long xol(Long a)
{
      if(a%2 == 0) {
            auto k = a/2;
            k = xo(k);
            return k * 2;
      }else {
            auto k = a/2;
            k = xo(k);
            return k * 2 + (((a/2) %2) == 0);
      }
      return 0;
}
int main()
{
      Di(q);
      for(int i= 0;i < q; i ++) {
            Long l,r;
            cin >> l >> r;
            cout << (xol(r) ^ xol(l-1)) << endl;
      }
      return 0;

}

LOJ 1279 – GRAPH COLORING

Category : Gaussian Elimination

Solution : k ^ (n- rank) % MOD;


/*

 *************************
 Id  : Matrix.code
 Task: 1279 – GRAPH COLORING
 Date: 2016-01-13

 **************************

 */

#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 SZ(a)                   (int) a.size()
#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 = 1000;
typedef Long T;
typedef vector<Long> VT;
typedef vector<VT> VVT;

void show(VVT &a)
{
      printf("PRINTING\n");
      for(int i = 0; i < SZ(a); i++)
      {
            for(int j = 0; j < SZ(a[0]); j ++ ) printf("%4d",a[i][j]);
            printf("\n");

      }

}

int gauss(VVT &a,Long k )
{
      int n= SZ(a) , m= SZ(a[0]) , r = 0;
      for(int c = 0 ; c < m-1 && r < n ; c ++ ) {
            int j = r;
            for(int i= j+1; i < n; i ++) if(a[i][c]) { j = i; break; }
            if(a[j][c] == 0 ) continue;
            swap(a[j],a[r]);
            T s = modinverse(a[r][c], k);
            for(int i = 0; i < m ; i++ ) a[r][i] = (a[r][i] * s) % k;
            for(int i = 0; i < n ; i ++ ) if(i!=r) {
                  if(a[i][c] == 0) continue;
                  Long t = a[i][c];
                  for(int j= 0; j < m; j ++ ) a[i][j] = ((a[i][j] - t * a[r][j]) % k + k ) % k;
            }
            r++;
            //show(a);
      }
      return r;
}
vector<int> G[N];
int main()
{

      //freopen("in.txt","r",stdin);

      Di(t);
      int cs = 0;
      while(t--) {
            Long n,m,k;
            scanf("%lld %lld %lld",&n,&m,&k);
            forn(i,m) {
                  Dii(a,b);
                  a--,b--;
                  G[a].pb(b);
                  G[b].pb(a);
            }
            VVT a(n,VT(n+1,0));
            for(int i =0 ;i < n ; i ++ ) {
                  a[i][i] = 1;
                  for(int j = 0; j < SZ(G[i]) ;j  ++) {
                        a[i][G[i][j]] = k-1;
                  }
                  a[i][n] = 0;
            }
            //show(a);
            int r = gauss(a,k);
            printf("Case %d: %lld\n" , ++cs , bigmod(k,n-r,1000000007LL));
            for(int i = 0; i < n; i ++ ) G[i].clear();
      }
      return 0;
}

GAUSSIAN ELIMINATION TO SOLVE MODULAR EQUATION

Category : GE
Sample Problem :

Uva 1358 – Generator

Category : String , Math , Probability. KMP

Solution:
As we can understand that, It is like chain dp.
How, Lets look,
I am allowed first two character and the patern is AAA. My dp state would be like

double calc(int pr);

pr = 0, initaily, Now we take a, taking a leads us to state calc(1) , because it matches with our first character.
Lets see the bellow diagram . We can easily find that there may occur loop in the graph.
How do we solve this?

This can be solved using gaussian elimination.
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 SZ(x)                   (int)x.size()
#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;}
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 IN(){    freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}

/*************************** END OF TEMPLATE ****************************/
const int N = 15;
int n;
int pf[N];
struct Frac{
      Long a,b;
      Frac(Long a=0,Long b=1){
            this->a=a,this->b=b;
            reduce();
      }
      void operator = (Long a) { this->a=a, this->b=1;}
      Frac operator + (const Frac &f) const {
            Long d = b / gcd(b,f.b) * f.b;
            Long n = a * d/b + f.a * d/f.b;
            Frac k = Frac(n,d); k.reduce();
            return k;
      }
      Frac operator - (const Frac & f) const {
            Frac k = f;
            k.a=-k.a;
            return *this + k;
      }
      Frac operator * (const Frac & f )const {
            Frac k ( a * f.a, b * f.b);
            k.reduce();
            return k;
      }
      Frac operator / (const Frac & f )const {
            Frac k ( a * f.b, b * f.a);
            k.reduce();
            return k;
      }
      bool operator < (const Frac &f) const {
            Frac k = *this-f;
            k.reduce();
            if(k.a<0) return 1;
            return 0;
      }
      bool isZero() { return a==0;}

      void reduce()
      {
            Long k = gcd(a,b);
            a/=k;
            b/=k;
            if(b<0) {b=-b,a=-a;}
      }
};


string s;
void comp(string &s,int psize)
{
      pf[0] = 0;
      for(int i = 1;i < psize; i ++) {
            int j = pf[i-1];
            while( j > 0 && s[i] != s[j]) j = pf[j-1];
            if(s[i] == s[j]) ++ j;
            pf[i] = j;
      }
}
int get(int pr,char c)
{
      while(pr > 0 && s[pr] != c) pr  = pf[pr-1];
      if(s[pr] == c) ++ pr;
      return pr;
}

typedef Frac T;
typedef vector<T> VT;
typedef vector<VT>VVT;

int Gauss(VVT &a)
{
      int n=SZ(a), m = SZ(a[0]), r = 0;
      for(int c = 0 ; c < m && r < n ; c ++ ) {
            int j = r;
            for(int i = r+1; i < n ; i ++ ) if(a[j][c] < a[i][c]) {j = i;}
            if(a[j][c].isZero ()) continue;
            swap(a[j], a[r]);
            T one = 1;
            T s = one / a[r][c];
            for(int i = 0; i < m ; i ++ ) a[r][i] = a[r][i] * s;
            for(int j = 0; j < n ; j ++ ) if(j!=r) {
                  T t = a[j][c];
                  for(int i=0; i < m ; i ++ ) a[j][i] = a[j][i] - t * a[r][i];
            }
            r++;
      }
      return r;
}
int main()
{

      //freopen("in.txt","r",stdin);
      Di(t);
      int cs= 0;
      while(t--) {
            Si(n);
            cin >> s;
            int l = s.length();
            comp(s,s.length());
            VVT a (l,VT(l+1,0));
            for(int i= 0;i < s.length();i ++ ) {
                  a[i][i] = 1;
                  for(int j = 0 ;j < n; j ++ ) {
                        int t = get(i,'A'+j);
                        a[i][t] = a[i][t] -  Frac(1,n);
                  }
                  a[i][l] = 1;
            }
            Gauss(a);
            if(cs) printf("\n");
            printf("Case %d:\n%lld\n" , ++cs, a[0][l].a );
      }
      return 0;
}

Gaussian Elimination

Category : Math

Discussion:
Gaussian Elimination is used to solve linear equations. This method can be applied to variety types of problem.
The basic of this method can be found in wiki and here

I use the code of stanford handnote. I modified it a bit.I am posting the modified code here.


typedef double T;
typedef vector<T> VT;
typedef vector<VT> VVT;


int Gauss(VVT &a)
{
	// AX = B;
	// Here n -> # of equations, m = number of column.The last column holds B. 
	// The function returns the rank of the matrix


	int n = a.size(), m= a[0].size();
	int r = 0;
	for(int c = 0; c < m - 1 && r < n ; c ++ ) {
		int j = r;
		for(int i = r+1; i < n; i ++ ) {
			if(fabs(a[i][c]) > fabs(a[j][c])) j= i;
		}
		if(fabs(a[j][c]) < EPS) continue;
		swap(a[j],a[r]);
		T s = 1./a[r][c];
		for(int i = 0; i < m ; i ++ ) a[r][i] *= s;
		for(int i=0;i < n ;i ++) if(i!=r) {
			T t = a[i][c];
			for(int j = 0; j < m ; j ++ ) a[i][j] -= t * a[r][j];
		}
		r++;
	}
	return r;

}

Applications of Gaussian Elimination is available in this page.

Problem Link : LOJ – 1151
This is a standard problem where we can use Gaussian Elimination. If you can not find the logic why to use GE, then look at the forum

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 SZ(x)                   (int)x.size()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-11
#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 IN(){    freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}

/*************************** END OF TEMPLATE ****************************/
const int N = 104;
int o[N];

typedef double T;
typedef vector<T> VT;
typedef vector<VT> VVT;


int Gauss(VVT &a)
{
	int n = a.size(), m= a[0].size();
	int r = 0;
	for(int c = 0; c < m - 1 && r < n ; c ++ ) {
		int j = r;
		for(int i = r+1; i < n; i ++ ) {
			if(fabs(a[i][c]) > fabs(a[j][c])) j= i;
		}
		if(fabs(a[j][c]) < EPS) continue;
		swap(a[j],a[r]);
		T s = 1./a[r][c];
		for(int i = 0; i < m ; i ++ ) a[r][i] *= s;
		for(int i=0;i < n ;i ++) if(i!=r) {
			T t = a[i][c];
			for(int j = 0; j < m ; j ++ ) a[i][j] -= t * a[r][j];
		}
		r++;
	}
	return r;

}
int main()
{

      //freopen("in.txt","r",stdin);
	Di(t);
	int cs= 0;
	while(t--) {
		Di(n);
		forn(i,101) o[i] = i;
		forn(i,n) {
			Dii(a,b);
			a--,b--;
			o[a] = b;
		}
		VVT a(100,VT(101,0));
		double p = 1./6;
		for(int i = 0; i < 99 ; i ++ ){
			a[i][i] = 1;
			for(int j = 1;j <= 6; j ++ ){
				int k = i + j;
				if(k < 100 ) a[i][o[k]] -= p;
				else a[i][i] -= p;
			}
			a[i][100] = 1;

		}
		a[99][99] = 1;
		a[99][100] = 0;

		int rank = Gauss(a);
		printf("Case %d: %.11lf\n", ++cs, a[0][100]);
	}
      return 0;
}

Another problem using same technique.
Link : Going To School
Just build the graph.And then run Gaussian Elimination.
My code link: http://paste.ubuntu.com/14456943/

Problem 3 : http://www.spoj.com/problems/LIM/
Solution Link : http://paste.ubuntu.com/14457124/

LightOJ – 1124 – Cricket Ranking

Category : PIE
Solution :
If We are not given any bound, then,
$x_1+x_2+x_3 = n ...... (1)$

How many Integer solution of this equation ?

This is Simply $\; \dbinom{n+k-1}{k-1}$

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) :

$y_1+p_1+y_2+p_2+y_3+p_3 = n \newline y_1 + y_2 + y_3 = n - p_1 - p_2 - p_3 ....... (2)$

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;
}

	Shakita Hallisey on Pick’s Theorem
	Madhu@1999 on LOJ – 1013 – Love…
	Optimus on SPOJ MKTHNUM – K-th…
	Optimus on SPOJ MKTHNUM – K-th…
	P☈∀⍡∈∈k J∀iN (@prate… on SPOJ MKTHNUM – K-th…

	Shakita Hallisey on Pick’s Theorem
	Madhu@1999 on LOJ – 1013 – Love…
	Optimus on SPOJ MKTHNUM – K-th…
	Optimus on SPOJ MKTHNUM – K-th…
	P☈∀⍡∈∈k J∀iN (@prate… on SPOJ MKTHNUM – K-th…

Code for Fun

Menu

Category Archives: Math

Fast Multiplication

HDU – 3032

When p = 1
we can move to only one position (0) , as 0 has grundy value of 0, then gr(1) = 1;

When p = 2
we can move to 0, 1, (1,1)(Spliting into 2 heap).

gr(2) = 2

When p = 3 we can move to 0, 1, 2,(1,2)(Spliting into 2 heap).

gr(3) = 4

When p = 4

gr(4) = 3

HDU – 4609 – 3-idiots

Table 1

Table 2

Xor-sequence

A1=1
A2=1⊕2
A3=1⊕2⊕3
A4=1⊕2⊕3⊕4
A5=1⊕2⊕3⊕4⊕5
…

B1=1
B2=2
B3=1⊕3
B4=2⊕4
B5=1⊕3⊕5
B6=2⊕4⊕6
B7=1⊕3⊕5⊕7
B8=2⊕4⊕6⊕8

LOJ 1279 – GRAPH COLORING

GAUSSIAN ELIMINATION TO SOLVE MODULAR EQUATION

Uva 1358 – Generator

Gaussian Elimination

LightOJ – 1124 – Cricket Ranking

CF 547C

Menu

When p = 1 we can move to only one position (0) , as 0 has grundy value of 0, then gr(1) = 1;

When p = 2 we can move to 0, 1, (1,1)(Spliting into 2 heap).

gr(2) = 2

When p = 3 we can move to 0, 1, 2,(1,2)(Spliting into 2 heap).

gr(3) = 4

When p = 4

gr(4) = 3

Table 1

Table 2

A1=1 A2=1⊕2 A3=1⊕2⊕3 A4=1⊕2⊕3⊕4 A5=1⊕2⊕3⊕4⊕5 …

B1=1 B2=2 B3=1⊕3 B4=2⊕4 B5=1⊕3⊕5 B6=2⊕4⊕6 B7=1⊕3⊕5⊕7 B8=2⊕4⊕6⊕8

When p = 1
we can move to only one position (0) , as 0 has grundy value of 0, then gr(1) = 1;

When p = 2
we can move to 0, 1, (1,1)(Spliting into 2 heap).

A1=1
A2=1⊕2
A3=1⊕2⊕3
A4=1⊕2⊕3⊕4
A5=1⊕2⊕3⊕4⊕5
…

B1=1
B2=2
B3=1⊕3
B4=2⊕4
B5=1⊕3⊕5
B6=2⊕4⊕6
B7=1⊕3⊕5⊕7
B8=2⊕4⊕6⊕8