Practice
Contest
Author:- Gaurav Katare
Tester:- Vivek Rathi
Difficulty:
Easy-Medium
PREREQUISITES:
matrix expo,combinatorics
Problem:
There are two options:
- Choose some number k. Considering all coins identical, give kk coins to Chotua. Next, treat remaining n−k coins as distinct and give k coins to Expert. Lets say there are p1 ways to do so for all possible k.
- Choose some number k. Considering all coins distinct, give k coins to Chotua. Next ,treat remaining n−k coins as identical and give k coins to =Expert. Lets say there are p2 ways to do so for all possible k.
Calculate the ratio of p1 and p2 . As this number can be rather large,he asks you to count the remainder after dividing it with 109+7
Explanation:
Since we have to distribute k coins to both friends so k belongs to [0,floor(n/2)].
Let find the value of p2, number of ways to distribute the k coins to both friends such that first all coins are distinct and then remaining n-k coins are identical are \binom{n}{k}.
So p2 = \sum_{k=1}^{N/2} \binom{n}{k}
As we know that \binom{n}{0} +…\binom{n}{n}= 2^n. For even numbers there are odd numbers of terms and for odd numbers there are even numbers of terms. In question it is mentioned that n is odd so we have exactly half of the terms, so \binom{n}{0}+\binom{n}{1}. +…\binom{n}{n/2} = 2^{n-1} . Since N is large we will use modular exponentiation.
Now let’s find the value of p1, number of ways to distribute the k coins to both friends such that first all coins are identical and then remaining n-k coins are distinct are \binom{n-k}{k}.
So p1=\sum_{k=1}^{N/2} \binom{n-k}{k}
For calculation of p1 construct pascal triangle.
\binom{0}{0}
\binom{1}{0} \binom{1}{1}
\binom{2}{0} \binom{2}{1} \binom{2}{2}
\binom{3}{0} \binom{3}{1} \binom{3}{2} \binom{3}{3}
\binom{4}{0} \binom{4}{1} \binom{4}{2} \binom{4}{3} \binom{4}{4}
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
We can observe that summation of diagonals of pascal’s triangle are in the form of Fibonacci and our equation is one of the diagonal . Hence p1=[N+1]th Fibonacci term. Since N is large so we can matrix exponential to calculate fibonacci terms.
The ratio of (p1/p2) \bmod 1000000007 will be the answer.
Time Complexity
Time Complexity per testcase is O(log(n))
Solution
Setter's Solution
/*
Gaurav Katare
*/
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long int
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define present(c,x) ((c).find(x) != (c).end())
#define null NULL
#define mp make_pair
#define sz(x) (ll)x.size()
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define inf 1e18
#define flush fflush(stdout);
#define endl '\n'
//unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
//shuffle (foo.begin(), foo.end(), std::default_random_engine(seed));
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
ll modpower(ll a,ll b,ll c)
{
ll res=1;
while(b)
{
if(b&1LL)
res=(res*a)%c;
a=(a*a)%c;
b>>=1;
}
return res;
}
//-------------------------------Template--Above-----------------------------------------------
struct matrix
{
#define SZ 2 // change here for matrix size
ll ar[SZ][SZ];
void reset()
{
memset(ar,0,sizeof(ar));
}
void makeidentity()
{
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
if(i==j)
ar[i][j]=1;
else
ar[i][j]=0;
}
}
}
matrix operator +(const matrix &o)// operator overloading of +
{
matrix res;
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
res.ar[i][j] = (ar[i][j] +o.ar[i][j])%M;
}
}
return res;
}
matrix operator *(const matrix &o)// operator overloading of *
{
matrix res;
res.reset();
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
for(int k=0;k<SZ;k++)
{
res.ar[i][j]=(res.ar[i][j]+(ar[i][k]*o.ar[k][j])%M)%M;
}
}
}
return res;
}
matrix power(matrix a,ll b)
{
matrix res;
res.makeidentity();
while(b)
{
if(b&1)
{
res=res*a;
}
a=a*a;
b>>=1;
}
return res;
}
};
int main()
{
boost
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
matrix m;
m.ar[0][0]=1,m.ar[0][1]=1;
m.ar[1][0]=1,m.ar[1][1]=0;
matrix sol=m.power(m,n-1);
ll ans=(sol.ar[0][0]+sol.ar[0][1])%M;
//debug1(ans2);
cout<<(ans*modpower(modpower(2,n-1,M),M-2,M))%M<<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ass 1e18
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define debug(x) cout << #x << ": " << x << endl;
#define debug2(x,y) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<< endl;
#define debug3(x,y,z) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<<" "<<#z<<" : "<<z<< endl;
using namespace std;
typedef long long int ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
ll modpower(ll a,ll b,ll c)
{
ll res=1;
while(b)
{
if(b&1LL)
res=(res*a)%c;
a=(a*a)%c;
b>>=1;
}
return res;
}
struct matrix
{
#define SZ 2 // change here for matrix size
ll ar[SZ][SZ];
void reset()
{
memset(ar,0,sizeof(ar));
}
void makeidentity()
{
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
if(i==j)
ar[i][j]=1;
else
ar[i][j]=0;
}
}
}
matrix operator +(const matrix &o)// operator overloading of +
{
matrix res;
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
res.ar[i][j] = (ar[i][j] +o.ar[i][j])%MOD;
}
}
return res;
}
matrix operator *(const matrix &o)// operator overloading of *
{
matrix res;
res.reset();
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
for(int k=0;k<SZ;k++)
{
res.ar[i][j]=(res.ar[i][j]+(ar[i][k]*o.ar[k][j])%MOD)%MOD;
}
}
}
return res;
}
matrix power(matrix a,ll b)
{
matrix res;
res.makeidentity();
while(b)
{
if(b&1)
{
res=res*a;
}
a=a*a;
b>>=1;
}
return res;
}
};
void solve()
{
ll n;
cin>>n;
matrix m;
m.ar[0][0]=1,m.ar[0][1]=1;
m.ar[1][0]=1,m.ar[1][1]=0;
m=m.power(m,n-1);
ll ans1=(((m.ar[0][0])%MOD)+((m.ar[0][1])%MOD))%MOD;
ll ans2=modpower(2,n-1,MOD);
cout<<(ans1*modpower(ans2,MOD-2,MOD))%MOD<<"\n";
}
int main()
{
boost
ll t=1;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>t;
while(t--)
{
solve();
}
return 0;
}