# CAC106 - CRACK-A-CODE 1.0 EDITORIAL

Krillin’s Function

Setter: mayureshpatle
Tester: mayureshpatle
Editorialist: mayureshpatle

EASY-MEDIUM

Recurrences

# PROBLEM:

K(0) = 0
K(n) = 7*K(n-1) + 3*n + 4 , for all n>0
Find the value of K(n)%1000000007 for given n.

# EXPLANATION:

For 60 points:
0 \leq n \leq10^6, so we can calculate K(n)%1000000007 for every 0 \leq n \leq10^6 and store each value in an array, say k[]. Then, we just need to read the value of n and output the stored value of k[n].

Time Complexity: O(N) for creating the array, each testcase will be answered in O(1)

Python Solution (for 60 points)
 k,n,mod=[0],10**6+1,10**9+7
for i in range(1,n):
k.append((7*k[-1]+3*i+4)%mod)
for _ in range(int(input())):
print(k[int(input())])


For Original Constraints:
Given recurrence equation is K(n) = 7*K(n-1) + 3*n + 4
This is a non-homogeneous recurrence equation having roots 7,1,1.

Therefore, K(n) = c_1*7^n + c_2*1^n + c_3*n*1^n,
i.e. K(n) = c_1*7^n + c_2 + c_3*n

• For n=0, K(0) = 0, using this we get,
0 = c_1 + c_2

• For n=1, K(1) = 7*K(0) + 3*n + 4 = 7, this gives
7 = c*7 + c_2 + c_3

• For n=2, K(2) = 7*K(1) + 3*n + 4 = 59, this gives
59 = c*49 + c_2 + c_3*2

By solving these three equations we get,
c_1 = 5/4, c_2 = -5/4, c_3 = -1/2

Using these values we can write
K(n) = (5*7^n - (5 + 2*n)) / 4

Now we calculate K(n)%1000000007 using this formula.

Time Complexity: O(log_2(N)) for modular exponentation.

# SOLUTIONS:

C++ Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll modex(ll x,ll p,ll m)
{
ll ans=1;
x=x%m;
while(p>0)
{
if(p&1) ans=(ans*x)%m;
p=p>>1;
x=(x*x)%m;
}
return ans;
}
int main()
{
ll t,n,f,s,nr,mod=1e9+7;
ll dr=modex(4,mod-2,mod);
cin>>t;
while(t--)
{
cin>>n;
f=(5*modex(7,n,mod))%mod;
s=(5+(2*(n%mod))%mod)%mod;
nr=(f-s+mod)%mod;
cout<<(nr*dr)%mod<<endl;
}
return 0;
}

Python Solution
mod=10**9+7
dr=pow(4,mod-2,mod)
for _ in range(int(input())):
n=int(input())
n=(5*pow(7,n,mod)-(5+2*n)%mod+mod)%mod
print((n*dr)%mod)

2 Likes

There is a better method for those who do not understand why recursives would be in that form
K(n)=7K(n-1)+3n+4 \\ K(n)-7K(n-1)=3n+4 \\ K(n) - 7K(n-1) + 7K(n-1) + 49K(n-2) ... =\sum_{i=1}^n (3i+4)*7^{n-i} = K(n) \\ \implies K(n)=3\sum_{i=1}^{n}{i*7^{n-i}} +4\sum_{i=1}^n {7^{n-i}} \\ \implies K(n) = 3\frac{(7^{n+1}-6n-7)}{36} + 4(\frac{7^n-1}{6}) \\ \implies K(n)=\frac{15 *7^n -6n -15}{12}=\frac{5*7^n -2n -5}{4}

1 Like