can someone pls tell me what edge case am i missing https://www.codechef.com/viewsolution/36216814

Can you explain your code for k = 3? Your code is hard to understand.

@therealnishuz

so i have used 3 dps which are inter connected

dp is the main dp

f[n] is for no of ways of covering 3n lenght grid but leaving one corner (either top or bottom both are included)

g[n] is for leaving 2 squares one int middle and the other either on top or bottom

main dp

i created the dp by taking cases of differnt end piece (ie 1*3 or 2*2 3*1) in length
so for end piece 1*3 we have dp[n-1]

for 3

*1 we can have in 2 ways ye can either have 3 3*1 pieces which would give dp[n-3] or we can club a 3

*1 an a 2*2 and here is the part where i used the dp f

a 3

*1 and 2*2 piece combided would fit a grid with 1 corner missing that is the dp of f

now to define f

i created it in the same way i created the main dp but 1*3 would work as in the last colummum there is 1 corner missing in f we can have 3 3*1 pieces so it would be f[n-3] and g[n-1] for using 2*2 as the last piece i noticed that any other set of pieces used as the last pieces would create gaps

now g

in g we can have 3 3*1 which gives g[n-3] or a combination of 3*1 and 2*2 to get dp[n-3] i multiplied it by 2 as i can arrage the 3*1 and 2*2 in 2 ways and f is not because it is based on g so it would be multiplied automatically

now we have defined everything so i ran a loop after defining the base cases to find dp[n]

i ran my code against an ac code for n=1 to 10000 and it gave the correct ans and even the dps kind of matched

this is a cleaner and main part of my code

ll dp[n+1]={0};

dp[1]=1;

dp[2]=1;

dp[3]=2;

dp[4]=3;

dp[5]=4;

dp[6]=8;

ll f[n+1]={0};

ll g[n+1]={0};

f[1]=0;

f[2]=0;

f[3]=0;

f[4]=2;

g[1]=0;

g[2]=0;

g[3]=2;

g[4]=2;

for(int i=5;i<7;i++){

f[i]=(f[i-3]+g[i-1])%1000000007;

g[i]=(2*dp[i-3]+g[i-3])%1000000007;
}
for(int i=7;i<n+1;i++){
f[i]=(f[i-3]+g[i-1])%1000000007;
g[i]=(2*dp[i-3]+g[i-3])%1000000007;

dp[i]=(dp[i-1]+f[i-2]+dp[i-3])%1000000007;

}

cout<<dp[n]<<le;

if you need any more explanation just ask me

There is an issue in your `dp[i]`

relation. You’re right about 1 1x3 tile and 3 3x1 tiles. But, you can stick a 2x2 on the top or bottom and the 3x1 will be where you don’t place it. Notice that they’re symmetric. So your relation for `dp[i]`

should be

dp_i = dp_{i-1} + dp_{i-3} + 2f_{something} (replace something with the correct value because it isn’t clear from your definition of f).

Also, use an ‘x’ to show multiplication. ‘*’ is for italics.

Just compare your answers with mine

## AC code

```
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const ll p=1e9 + 7;
struct matrix{
vector<vector<ll>> mat;
matrix(int n, int m){
mat.resize(n,vector<ll>(m));
}
matrix operator*(matrix a){
matrix ans(this->mat.size(),a.mat[0].size());
for(int i=0;i<this->mat.size();i++){
for(int j=0;j<a.mat[0].size();j++){
for(int k=0;k<a.mat.size();k++){
ans.mat[i][j]+=(this->mat[i][k]*a.mat[k][j])%p;
ans.mat[i][j]%=p;
}
}
}
return ans;
}
};
matrix matpower(matrix base,ll power){
matrix ans(base.mat.size(),base.mat.size());
for(int i=0;i<base.mat.size();i++){
ans.mat[i][i]=1;
}
while(power){
if(power & 1){
ans=ans*base;
}
base=base*base;
power>>=1;
}
return ans;
}
void solve2(){
int n;
cin>>n;
matrix init(1,3);
init.mat={{1,0,1}};
matrix base(3,3);
base.mat={
{0,0,1},
{1,0,1},
{0,1,0}
};
cout<<(init*matpower(base,n)).mat[0][0]<<"\n";
}
void solve(){
int n;
cin>>n;
matrix init(1,9);
init.mat={{1,0,0,1,0,0,2,0,2}};
matrix base(9,9);
base.mat=
{
{0,0,0,0,0,0,1,0,2},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,1,0,0},
{0,0,1,0,0,0,0,0,0},
{0,0,0,1,0,0,1,0,0},
{0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,1,0}
};
cout<<(init*matpower(base,n-1)).mat[0][0]%p<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
//precompute();
while(t--){
int k;
cin>>k;
if(k==3){
solve();
}
else if(k==1){
int n;
cin>>n;
cout<<(n%3==0)<<"\n";
}
else{
solve2();
}
}
}
```

The answer should diverge before 10

If it doesn’t then it is overflow or you’ve written 1000000007 wrong somewhere

Also learn latex

i solved the prob thanks everyone for replying