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.
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!
