CAC106 - CRACK-A-CODE 1.0 EDITORIAL

editorial
, , ,
1

PROBLEM LINK:

Krillin’s Function

Setter: mayureshpatle
Tester: mayureshpatle
Editorialist: mayureshpatle

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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
2

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