 # MATBREAK - Editorial

Contest

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

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);
prod = mul(prod, inc);
}
printf("%d\n", ans);
}
}

Tester's Solution
//raja1999

//#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 9 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={0};
facto=1;
for(lli i=1;i<=100000;i++)
facto[i] = modmul2(i,facto[i-1]);

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

lli dp;
dp=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++){
}
cout<<sumi<<endl;

}
return 0;
}
12 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 .

36 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. 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
1 Like

Thankyou okay thankyou 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.

#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=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.

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.
@rajarshi_basu

Simple video editor of MATBREAK https://youtu.be/c-Ox8mwU6yg

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 basic=1;
for(int i = 1 ; i <= n ;i++){
ll l=expo(kbasic,2i-1);
l=l%M;