CSUMD-TLE :(

general
1

i had my code, with the same solution as provided in the editorial, during the competition, sill getting TLE :frowning: plzz help. what am, i doing wrong.

#include<stdio.h>
#include <vector>
#include<map>
#define REP(i,n) for (int i = 1; i <= n; i++)
using namespace std;
typedef unsigned long long ll;
typedef vector<vector<ll> > matrix;
inline void inp( ll &n )//fast input function
{
        n=0;
        ll ch=getchar();
        while(  ch >= '0' && ch <= '9' )
                n = (n<<3)+(n<<1) + ch-'0', ch=getchar();
}
#define MOD 10000000007ULL;
int K = 2;
 
inline matrix mul(matrix A, matrix B)
{
    matrix C(K+1, vector<ll>(K+1));
    C[1][1]=((A[1][1]*B[1][1])+ (A[1][2]*B[2][1]))%MOD;
    C[1][2]=((A[1][1]*B[1][2])+ (A[1][2]*B[2][2]))%MOD;
    C[2][1]=((A[2][1]*B[1][1])+ (A[2][2]*B[2][1]))%MOD;
    C[2][2]=((A[2][1]*B[1][2])+ (A[2][2]*B[2][2]))%MOD;
   /* REP(i, K) REP(j, K) REP(k, K)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;*/
    return C;
}
matrix pow(matrix A, ll p)
{
    if (p == 1)
    {
        return A;
    }
    if ((p % 2)!=0)
    {
 
        return mul(A, pow(A, p-1));;
    }
        else
        {
        matrix X = pow(A, p/2);
        return mul(X, X);
        }
}
inline ll fib(ll N)
{
    vector<ll> F1(K+1);
    F1[1] = 1;
    F1[2] = 3;
    matrix T(K+1, vector<ll>(K+1));
    T[1][1] = 0, T[1][2] = 1;
    T[2][1] = 2, T[2][2] = 2;
    if (N == 1)
        return 1;
    T = pow(T, N-1);
    ll res = 0;
    REP(i, K)
        res = (res + T[1][i] * F1[i]) % MOD;
    return res;
 
}
 
int main()
{
    ll n,m,test;
    inp(test);
    for(;test>0;test--)
    {
     inp(n);
    printf("%lld\n",fib(n));
    }
    return 0;
}
2

Iā€™m not C++ expert, but Iā€™d say, that int[2][2] is quicker than vector[3][3], but first thing you can try, is to perform MOD operations only when needed:

replace:

C[1][1]=((A[1][1]*B[1][1])+ (A[1][2]*B[2][1]))%MOD;

with

C[1][1]=(A[1][1]*B[1][1])+ (A[1][2]*B[2][1]);
if (C[1][1] >= MOD ) C[1][1] %= MOD;

same in fib function

1 Like
3

I remember I too got a two TLE during the contest,then I rewrite the code,without using any STL .So as @betlista said, replacing the Vector(STL) with array will surely help u in Removing the TLE.

1 Like