Can you explain how did you came across this recurrence?
Can somebody please tell me why my code is not working? I have tested on some of my test cases but it fails on the system test case. Thanks for your help.
Here is the line: #include <bits/stdc++.h>using namespace std;#define ms(x, t) memset(x, t, si - Pastebin.com
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector vl;
const int mod = 1e9 + 7;
vector matI(int n) {
vector I(n, vl(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
I[i][j] = 1;
}
}
return I;
}
vector matMul(vector &a, vector &b) {
ll n = a.size();
ll m = b[0].size();
ll l = b.size();
vector c(n, vl(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < l; k++) {
c[i][j] = (c[i][j] + (a[i][k] % mod * b[k][j] % mod) % mod) % mod;
}
}
}
return c;
}
vector matExp(ll n, vector &a) {
int m = a.size();
vector ans = matI(m);
while (n) {
if (n & 1) {
ans = matMul(a, ans);
}
a = matMul(a, a);
n = n >> 1;
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin >> t;
while (t–) {
ll n, m;
cin >> n >> m;
// vector<vl> y = {{1, 2, 3}, {4, 5, 6}, {2, 1, 3}};
// vector<vl> z = {{1, 2}, {4, 5}, {2, 1}};
// vector<vl> e = matMul(y, z);
// for (auto x : e) {
// for (auto y : x) {
// cout << y << " ";
// }
// cout << endl;
// }
vector<vl> p = {{m - 1, m - 1}, {1, 0}};
vector<vl> a = {{m}, {0}};
vector<vl> e = matExp(n - 1, p);
vector<vl> res = matMul(e, a);
cout << (res[0][0] + res[1][0]) % mod << endl;
}
return 0;
}
I followed the recursive approach for this problem as mentioned but still couldn’t pass subtask 1, pls help me find the mistake in my code
#include <bits/stdc++.h>
#define modulo 1000000009
using namespace std;
int f(int n, int m,int val){
if(n==1){
if(val==1)
return m% modulo;
else
return 0;
}
if(val==1){
return (((m-1)%modulo)*((f(n-1,m,1)+f(n-1,m,2))))%modulo;
}
if(val ==2){
return f(n-1,m,1)%modulo;
}
}
int main() {
int t;
cin>>t;
while(t–){
int n, m;
cin>>n>>m;
int count=f(n,m,1)+f(n,m,2);
cout<<count<<endl;
}
}
somebody help me to resolve the problem.I had done exactly same as described in the editorial
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector>& matrix;
ll mod=1e9+7;
void multiply(matrix A,matrix B){
ll n=A.size();
vector<vector>temp;
temp.resize(n);
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
ll sum=0;
for(ll k=0;k<n;k++){
sum+=A[i][k]*B[k][j];
sum%=mod;
}
temp[i].push_back(sum);
}
}
for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) B[i][j]=temp[i][j];
return;
}
void power(matrix mat,matrix res,ll k){
if(k==0) return;
if(k==1){
ll n=mat.size();
for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) res[i].push_back(mat[i][j]%mod);
return;
}
power(mat,res,k/2);
multiply(res,res);
if(k&1) multiply(mat,res);
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;
while(t–){
ll n,m;
cin>>n>>m;
if(n==1){
cout<<m%mod<<"\n";
continue;
}
vector<vector>mat{{m-1,m-1},{1,0}},res;
res.resize(2);
power(mat,res,n-1);
ll ans=(res[0][0]+res[1][0])%mod;
ans=(ans*m)%mod;
cout<<ans<<"\n";
}
return 0;
}
Yes sure,
Let f(i) be the count of valid array of length i, then there will be two cases
(i) either arr[i-1]==arr[i-2]
then at ith position we have m-1 choices along with string of length i-3.
which will be equal to f(i-3)*(m-1)
(ii) or arr[i-1]!=arr[i-2]
here we have no restrictions so this will be f(i)*m
finally, f(i) = f(i-1)m + f(i-3)(m-1)
I am not sure whether my solution is correct or not, This is what i came up with during the contest.
1 Like
I think you are using inclusion -excluson principle which is giving wrong results
try n=5 and m=8 which is giving 31352 but answer is 31360
You used too much modulo operations.
I came across the same recurrence can’t comprehend how to solve this in log (n) ;/.
Could you explain what these statements do?
Thanks in advance.
relation will be
dp[i] = dp[i-1]m - dp[i-3](m-1) for i>3
Here is the video link where I have discussed the algorithm for this question in the best possible time complexity :- YouTube 
:
Please go through it and do like and share if u find it helpful 
1 Like
Well explained dude !!
Hi,
I was not able to understand how we have (m-1) choices when the last two elements are different[f(i,1)=(M−1)∗(f(i−1,1)+f(i−1,2))]?. I can see why it is (m-1) choices for f(i-1,2) but If the last two elements are different then the current element can be any of the ‘m’ choices?.
I am using the exact same recurrence, but I am getting both WA and TLE.
This is my submission.
Could someone tell me why this is wrong?
https://www.codechef.com/viewsolution/34698788
please help please i am getting tle after applying matrix exponentiation
please some one please help @taran_1407 @teja349
I thought it was a pnc question 
You should implement matrix exponentiation approache without recursion.
An awesome problems with an awesome editorial !!
I used a vector implementation and it took more than 1s (1.34s to be exact) to run whereas it took just 0.21 s in the global 2D array implementation.
If the time limit was 1sec instead of 2 sec, my first AC code would have given TLE.
One of the advantages of vectors is that they can be passed very easily (in comparison to 2D arrays).
So I am looking for some optimization with which I can get that fast runtime with vectors (not by defining them globally) ?