MATBREAK - Editorial

PROBLEM LINK:

Contest

Author: Ayush Ranjan
Tester: Raja Vardhan Reddy
Editorialist: Rajarshi Basu

DIFFICULTY:

Simple

PREREQUISITES:

Fast Exponentiation, Implementation


PROBLEM:

We are given an N\times N matrix (call it M) (1 \leq N \leq 10^5) with all elements set to a initially. In each iteration i, we choose all cells M_{x,y} where min(x,y) = N-i . Let the product of numbers written in these cells be P_i. Next, we multiply all remaining cells by P_i, and move on to the next iteration. We need to report S = P_1 + P_2 + P_3 + ... P_n

(For a visual perspective, quickly see the image in the problem).

QUICK EXPLANATION:

Let the i^{th} odd number be x. Since we multiply all cells by P_j (j < i), all the values of the cells considered in i^{th} iteration are still of same: a_i = a *P_{tot}, where P_{tot} = \displaystyle\prod_{j=1}^{i-1} P_j.Therefore,P_i = a_i ^ {x}. Maintain P_{tot} , and add all P_i and we are done.


DETAILED EXPLANATION:

I will elaborate the solution in terms of step-by-step observations.

Observation 1

N can go up to 10^5, we cannot create a N\times N matrix due to memory constraints. Hence, simulating the algorithm is not possible, and there must be something easier.

Observation 2

In each step, all remaining cells will have the same value. In particular in the i^{th} step all ! cells will have value a_i = a *P_{tot}, where P_{tot} = \displaystyle\prod_{j=1}^{i-1} P_j.

Implementation Detail 1

We can actually maintain P_{tot} easily, since P_{tot:i} = P_{tot: i-1} * P_i , where P_{tot: j} means value of P_{tot} in j^{th} iteration. Hence, after computing P_i in the i^{th} iteration, we just multiply P_{tot} with P_i and move on to the next iteration.

Observation 3

We can see that in the i^{th} iteration, we will be considering x cells, where x is the i^{th} odd number. How? See the diagram, and try to reason why.

Observation 4

Since we are multiplying the same value x times, it is the same thing as exponentiating. Hence, we can say that P_i = (a*P_{tot :i})^x = a_i^x.

Implemenation 2

How to exponentiate any value to a specific power quickly? Click and Click

Final Touches

Now that we have computed all values of P_i, add them up. Print them. Done.


Time Complexity

Keeping track of P_{tot} takes O(1) time per iteration, while exponentiating to find each P_i takes O(logn) time. Hence, overall for N iterations, the total time complexity is O(nlogn).

QUICK REMINDERS:

Don’t forget to use modular arithmetic!

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
const int mod=1e9+7;
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
 
int main()
{
	int t;
	scanf("%d", &t);
	while(t--){
		int n, a;
		scanf("%d%d", &n, &a);
		int ans = 0, prod = 1;
		for(int i = 0; i < n; i++){
			int inc = power(mul(a, prod), 2 * i + 1);
			ans = add(ans, inc);
			prod = mul(prod, inc);
		}
		printf("%d\n", ans);
	}
} 
Tester's Solution
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
int power(int a,int b){
	a%=mod;
	int res=1;
	while(b>0){
		if(b%2){
			res*=a;
			res%=mod;
		}
		a*=a;
		a%=mod;
		b/=2;
	}
	return res;
}
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,a,prod,val,ans=0,i;
		cin>>n>>a;
		prod=1;
		f(i,1,n+1){
			val=power(a*prod,2*i-1);
			val%=mod;
			ans+=val;
			ans%=mod;
			prod*=val;
			//cout<<prod<<" "<<ans<<endl;
			prod%=mod;
		}
		cout<<ans<<endl;
	}
	return 0;
} 
Editorialist's Solution
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define vv vector
 
using namespace std;
 
const int INF = 1e9;
const int MAXN = 1e5+5;
const ll MOD = 1e9 + 7;
 
ll fxp(ll a, ll b){
	if(b == 0)return 1;
	if(b%2 == 0){
		ll c = fxp(a,b/2);
		return (c*c)%MOD;
	}
	return (a*fxp(a,b-1))%MOD;
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		ll n,a;
		cin >> n >> a;
		ll num = 1;
		ll sum = 0;
		ll p = 1;
		FOR(i,n){
			ll pp = fxp((a*p)%MOD , num);
			num += 2;
			p *= pp;
			p %= MOD;
			sum += pp;
			sum %= MOD;
		}
		cout << sum << endl;
	}
 
	return 0;
} 

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

10 Likes

Great explaination … i found the series in power which is

1 6 40 336 3456  {formula = (2^i)(i!)(2*i +1)  0<=i<=100000 }

https://oeis.org/A014481

Now most important thing is to calculaate (a^b)%m { where b is from above series which can be very large )
to find this we can do (a^(b%(m-1))%m like this : https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/

  #include<bits/stdc++.h>
  using namespace std;
  #define mod 1000000007
  ll modmul(ll a, ll b) {
     return ((a%mod) * (b%mod)) % mod;
   }
  ll modmul2(ll a, ll b) {
    return (((a%(mod-1)) * (b%(mod-1))) % (mod-1));
   }
  ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
   }
int main(){
lli t=1;
cin>>t;
lli facto[100005]={0};
facto[0]=1;
for(lli i=1;i<=100000;i++)
    facto[i] = modmul2(i,facto[i-1]);

lli pw2[100005]={0};
pw2[0]=1;
for(lli i=1;i<=100000;i++)
    pw2[i] = modmul2(2,pw2[i-1]);

lli dp[100005];
dp[0]=1;
for(lli i=1;i<=100000;i++){
    dp[i] = modmul2(modmul2(pw2[i],facto[i]),(2*i +1));
}

while(t--) {
    lli n,a;
    cin>>n>>a;
    lli sumi = 0;
    for(lli i=1;i<=n;i++){
        sumi = modadd(sumi , fastexpo(a,dp[i-1]));
    }
    cout<<sumi<<endl;
	
}
return 0;
}
13 Likes

I just wanted to ask why problem setter don not read comments posted by some coders .It seems they are completely ignoring their doubts just because of some statement clarification???

5 Likes

#include <bits/stdc++.h>
#include
using namespace std;
long long int powerr(long long int x,unsigned int y, int p)
{
long long int res = 1; // Initialize result

x = x % p; // Update x if it is more than or
            // equal to p

if (x == 0) return 0; // In case x is divisible by p;

while (y > 0)
{
    // If y is odd, multiply x with result
    if (y & 1)
        res = (res*x) % p;

    // y must be even now
    y = y>>1; // y = y/2
    x = (x*x) % p;
    //cout<<res<<" ";
}
return res;

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int mod=1000000007;
int t;
cin>>t;
while(t–)
{
long long int n,a;
cin>>n>>a;
long long int sum=a;
unsigned int pow=1,pows=1;
for(int i=2;i<=n;i++)
{
pow=(1+pows)(2i-1);
pow=pow%(mod-1);
pows+=pow;
pows=pows%(mod-1);
sum+=powerr(a,pow,mod);
sum=sum%mod;
}

    cout<<sum<<"\n";
}

}

Could you guys please tell what is wrong in my code??

Guys I think Codechef should make all test cases visible for 5-6 hours after a contest so that we can work on where we went wrong and no need to all to problemsetter.This will be beneficial I think .

37 Likes

can anyone just help me find what i did wrong
@rajarshi_basu @ssrivastava990

https://www.codechef.com/viewsolution/32067258

@pavanrajshetty in the power function for a larger value like 10 ˆ 20 will not be evaluated as needed it will evaluate some negative value. thus we needed a function for power and modulo Modular Exponentiation
that u can find here it will do the task for u. :slight_smile:

2 Likes

you should calculate power using your self power function and take modulo%1000000007 at every step, because for large value of A your power function will give 0 as output.

2 Likes

video explanation to MATBREAK problem

1 Like

Thankyou :slight_smile:

okay thankyou :slight_smile:

Can anyone please tell whats wrong with my solution. It works fine with n=3 & a=2.
But it gives negative answer for n=3 & a=4 and many more cases.
PLEASE HELP!

#include<bits/stdc++.h>
#define ll long long int
#define li long int
using namespace std;

int main()
{
        ll n,a;
        cin>>n>>a;
        ll p[n];
        p[1]=a;
        for(ll i=2;i<=n;++i)
        {
            p[i]= pow((p[i-1] * a),(2*i)-1);
            a= a*p[i-1];
        }

        ll tmp=0;

        for(ll i=1;i<=n;++i)
             tmp+=p[i];

        cout<<tmp%1000000007<<"\n";
	return 0;
}

you should calculate power using your self power function and take modulo%1000000007 at every step, because for large value of a your power function will give 0 as output.
refer this link->Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks

2 Likes

can someone explain me as how can i resolve the issue of evaluating negative no in the pow function…this is my code
#include<bits/stdc++.h>

#define M 1000000007

using namespace std;

long long pow(long long no,long long power)

{

if(power == 1)

return no;

else if(power == 0)

return 1;

long long R = pow(no,power/2)%M;

R = R*R%M;

if(power%2 != 0)

{

    R = R*no%M;

}

return R%M;

}

int main()

{

int t;

cin >> t;

while(t--)

{

    int n;

    long long a;

    cin >> n;

    cin >> a;

    long long no = a;

    long long sum = 0;

    long long pro;

    for(int i = 1;i<=n;i++)

    {

        pro = pow(no,2*i-1);

        //cout << "pro1 : " << pro << endl;

        pro = pro%M;

        //cout << "pro2 : " <<pro << endl;

        if(pro<0)

            pro += M;

        sum  = (sum+pro)%M;

        no = (no*pro)%M;

    }

    cout << sum << endl;

}

return 0;

}

How did you arrive at this series?

https://www.codechef.com/viewsolution/32075109

can somebody help why i was getting TLE in this solution .

Any help would be very very helpful.
Thanks in advance
@rajarshi_basu

Simple video editor of MATBREAK :smile:

Matrix Decomposition || April Cook-Off 2020 Division 2 || c++ solution - YouTube

It gives *** the wrong answer***. Can anyone see my code and tell me what is wrong in my code?

#include<bits/stdc++.h>
#define M 1000000007
typedef long long ll;
using namespace std;
ll expo(ll a , ll b){
ll ans=1;
while(b){
if(b&1){
ans=(ansa)%M;
}
a=(a
a)%M;
b>>=1;
}
// cout<<ans<<endl;
return ans;
}
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
ll answer=0;
ll basic=1;
for(int i = 1 ; i <= n ;i++){
ll l=expo(kbasic,2i-1);
l=l%M;
answer=(answer+l)%M;
basic=(basic*l)%M;
// cout<<answer<<endl;
}
cout<< answer%M;
}}

thanks!

It had a minor flaw. I did it.
Thanks anyways.