Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Stepping Numbers CodeChef Solution

Problem -Stepping Numbers CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Stepping Numbers CodeChef Solution in C++17


#include <stdio.h> 
#include <stdlib.h> 

#define ullint unsigned long long
#define uint unsigned int 

#define MOD 4294967143ULL
#define MODINV 1789569643ULL

typedef struct {
    ullint a;
    ullint b;
} surd;

inline ullint modprod(ullint a, ullint b) {
    return (a*b) % MOD;
}

inline ullint modminus(ullint a, ullint b) {
    a = a % MOD;
    b = b % MOD;
    if (a >= b)
        return a - b;
    else
        return (MOD - b) + a;
}

inline surd mult(surd s1, surd s2) {
    surd res;
    res.a = (modprod(s1.a,s2.a) + modprod(modprod(s1.b,s2.b),3)) % MOD;
    res.b = (modprod(s1.a,s2.b) + modprod(s1.b,s2.a)) % MOD;
    return res;
}


ullint p3array[65];
ullint p2array[65];
surd surdarray[65];

void init() {
    p2array[1] = 2;
    p3array[1] = 3;
    surdarray[1].a = 2;
    surdarray[1].b = 1;
    for(int i = 2; i < 65; i++) {
        p2array[i] = modprod( p2array[i-1] , p2array[i-1] );
        p3array[i] = modprod( p3array[i-1] , p3array[i-1] );
        surdarray[i] = mult(surdarray[i-1],surdarray[i-1]);
    }
}

void solve(ullint a) {

    if (a == 0 || a % 2 == 1) {
        printf("0\n");
        return;
    }

    a = a >> 1;

    ullint p2 = 1;
    ullint p3 = 1;
    surd ps;
    ps.a = 1;
    ps.b = 0;

    int i = 1;
    while(a > 0) {
        if ( (a & 1) == 1) {
            p2 = modprod(p2, p2array[i]);
            p3 = modprod(p3, p3array[i]);
            ps = mult(ps,surdarray[i]);
        }
        i++;
        a = a >> 1;
    }

    surd psminus;
    psminus.a = modminus(2*ps.a, 3*ps.b);
    psminus.b = modminus(2*ps.b, 3*ps.a);

    ullint res1 = modprod(MODINV, (2*psminus.a + p3 + 2*p2 + 3) % MOD );
    ullint res2 = 2*(2*ps.a + p3 + p2 + 1);
    
    ullint res = modminus(res2, res1);
    printf("%llu\n", res);
}

main() {

    int T;
    scanf("%d", &T);

    int i;
    init();
    for(i = 0; i < T; i++) {

        ullint a;
        scanf("%llu", &a);

        solve(a);
    }
}

Stepping Numbers CodeChef Solution in C++14

#include <stdio.h> 
#include <stdlib.h> 

#define ullint unsigned long long
#define uint unsigned int 

#define MOD 4294967143ULL
#define MODINV 1789569643ULL

typedef struct {
    ullint a;
    ullint b;
} surd;

inline ullint modprod(ullint a, ullint b) {
    return (a*b) % MOD;
}

inline ullint modminus(ullint a, ullint b) {
    a = a % MOD;
    b = b % MOD;
    if (a >= b)
        return a - b;
    else
        return (MOD - b) + a;
}

inline surd mult(surd s1, surd s2) {
    surd res;
    res.a = (modprod(s1.a,s2.a) + modprod(modprod(s1.b,s2.b),3)) % MOD;
    res.b = (modprod(s1.a,s2.b) + modprod(s1.b,s2.a)) % MOD;
    return res;
}


ullint p3array[65];
ullint p2array[65];
surd surdarray[65];

void init() {
    p2array[1] = 2;
    p3array[1] = 3;
    surdarray[1].a = 2;
    surdarray[1].b = 1;
    for(int i = 2; i < 65; i++) {
        p2array[i] = modprod( p2array[i-1] , p2array[i-1] );
        p3array[i] = modprod( p3array[i-1] , p3array[i-1] );
        surdarray[i] = mult(surdarray[i-1],surdarray[i-1]);
    }
}

void solve(ullint a) {

    if (a == 0 || a % 2 == 1) {
        printf("0\n");
        return;
    }

    a = a >> 1;

    ullint p2 = 1;
    ullint p3 = 1;
    surd ps;
    ps.a = 1;
    ps.b = 0;

    int i = 1;
    while(a > 0) {
        if ( (a & 1) == 1) {
            p2 = modprod(p2, p2array[i]);
            p3 = modprod(p3, p3array[i]);
            ps = mult(ps,surdarray[i]);
        }
        i++;
        a = a >> 1;
    }

    surd psminus;
    psminus.a = modminus(2*ps.a, 3*ps.b);
    psminus.b = modminus(2*ps.b, 3*ps.a);

    ullint res1 = modprod(MODINV, (2*psminus.a + p3 + 2*p2 + 3) % MOD );
    ullint res2 = 2*(2*ps.a + p3 + p2 + 1);
    
    ullint res = modminus(res2, res1);
    printf("%llu\n", res);
}

main() {

    int T;
    scanf("%d", &T);

    int i;
    init();
    for(i = 0; i < T; i++) {

        ullint a;
        scanf("%llu", &a);

        solve(a);
    }
}


Stepping Numbers CodeChef Solution in C

#include <stdio.h>

#define MOD 4294967143U

typedef unsigned int intu;
typedef unsigned long long longu;

longu s1[64],s2[64];

intu pmod(int a, longu n)
{
    intu t;
    longu s;

    s=a;
    t=1;

    while(n)
    {
        if (n&1)
            t=(s*t)%MOD;
        s=(s*s)%MOD;
        n>>=1;
    }
    return t;
}


intu pot(longu n)
{
    longu q;
    intu t1,t2;
    int i;

    t1=1;
    t2=0;

    for(i=0;n;n>>=1,i++)
        if (n&1)
        {
            q=t1;
            t1=(s1[i]*t1%MOD+3*(s2[i]*t2%MOD))%MOD;
            q=s1[i]*t2%MOD+s2[i]*q%MOD;
            if (q>=MOD)
                t2=q-MOD;
            else
                t2=q;
        }

    return (94LL*t1+144LL*t2)%MOD;
}

int main()
{
    int t,i;
    longu n;

    s1[0]=2;
    s2[0]=1;
    for(i=1;i<64;i++)
    {
        s1[i]=(s1[i-1]*s1[i-1]%MOD+3*(s2[i-1]*s2[i-1]%MOD))%MOD;
        s2[i]=2*(s1[i-1]*s2[i-1]%MOD)%MOD;
    }



    scanf("%d",&t);

    while(t--)
    {
        scanf("%llu",&n);

        if (n&1)
        {
            printf("0\n");
            continue;
        }
        n=n-1>>1;

        printf("%llu\n",(21+11LL*pmod(2,n+2)+23LL*pmod(3,n+1)+pot(n))%MOD*1789569643%MOD);
    }
    return 0;
}
Stepping Numbers CodeChef Solution Review:

In our experience, we suggest you solve this Stepping Numbers CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Stepping Numbers CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Stepping Numbers CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *