[Solved] Fibonacci concatenation solution codechef 

Fibonacci concatenation solution codechef


Let’s define Fibonacci concatenation sequence as follows:

  • f[0]=0f[0]=0f[1]=1f[1]=1

  • f[i]=f[i1]+f[i2]f[i]=f[i−1]+f[i−2], for every i2i≥2

Here f[i]f[i] denotes the ithith Fibonacci concatenation number and ++ represents concatenation.

For example, f[2]=f[1]+f[0]=1+0=10f[2]=f[1]+f[0]=1+0=10f[3]=f[2]+f[1]=f[3]=f[2]+f[1]= 10+1=10+1= 101101.

Given an integer nn, you have to determine the sum of digits of all subsequences of the nthnth Fibonacci concatenation number f[n]f[n], modulo 109+7109+7.

subsequence of a number is a sequence of digits that can be derived from the number by deletion of several (possibly, zero or all) digits without changing the order of the remaining digits. The subsequence may even start with trailing zeros. For example 10100101 are subsequences of 101101 while 110110 is NOT a subsequence of 101101. Note that there are 88 subsequences of 101101. The subsequence 11 appears twice and should be counted as different while computing the sum.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains a single integer nn.

Output Format

For each test case, print a single line containing one integer – the sum of digits of all subsequences of f[n]f[n], modulo 109+7109+7.

Constraints

  • 1T1051≤T≤105
  • 1n1051≤n≤105

Sample Input 1 

3
1
2
3

Sample Output 1 

1
2
8

Explanation

Test case 11: Since f[1]=1f[1]=1, we have only two subsequences, “” (empty subsequence) and “11“. So the sum of digits of both subsequences is 0+1=10+1=1.

Test case 22: Since f[2]=10f[2]=10, we have four subsequences, “” (empty subsequence), “11“, “00” and “1010“. So the sum of digits of all the subsequences is 0+1+0+1=20+1+0+1=2.


Solution 


Python

dp = [0]*(100000+2)
fibPow = [0]*(100000+2)
fibPow[0] = 2
fibPow[1] = 2
dp[1] = 1
m=1000000007

for i in range(2, 100000+2):
# print(fib[i-1], fib[i-2], pow[fib[i-1]], pow[fib[i-2]])
fibPow[i] = (fibPow[i-1]*fibPow[i-2])%m
dp[i] = (((dp[i-1]*fibPow[i-2])%m)+((dp[i-2]*fibPow[i-1])%m))%m
# print(i, dp[i])

for _ in range(int(input())):
n = int(input())
print(dp[n])


C++

#include <bits/stdc++.h>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;

#define int long long int
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define ms1(dp) memset(dp, -1, sizeof(dp));
#define ms0(dp) memset(dp, 0, sizeof(dp));
#define minheap int, vector<int>, greater<int>
#define setbits(x) __builtin_popcountll(x) //count number of 1
#define zrobits(x) __builitin_ctzll(x) //count number of zero before 1st 1 ex- (110000)2 ->4
#define MOD 1000000007
#define ps(x, y) fixed << setprecision(y) << x
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ROF(i, a, b) for (int i = a; i >= b; i–)
#define endl “\n”
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define INF 2e18
#define fast_cin() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define ALL(x) (x).begin(), (x).end()
int power(int x,int y)
{
int res=1;
x=x%MOD;
while(y>0)
{
if(y&1)
res=(res*x)%MOD;

y=y>>1;
x=(x*x)%MOD;
}
return res;
}

int32_t main()
{
fast_cin();
vector<int> arr(100002);
arr[0]=0;
arr[1]=1;
for(int i=2;i<=100001;i++)
{
arr[i]=(arr[i-1]%MOD+arr[i-2]%MOD)%MOD;
}
vector<int> kk(100002);
kk[0]=1;
kk[1]=1;
for(int i=2;i<=100001;i++)
{
kk[i]=(kk[i-1]%(MOD-1)+kk[i-2]%(MOD-1))%(MOD-1);
}
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int d=arr[n];

int z=power(2,kk[n]-1);
int ans=(d*z)%MOD;
cout<<ans<<endl;
}
return 0;
}


Also read : Black cells in a chessboard solution codechef

Also read : Large Square solution codechef

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef 

Fibonacci concatenation solution codechef 

 

No Comments, Be The First!

Your email address will not be published.