PROBLEM LINK:
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.
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 
