CKVIRS - EDITORIAL

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Pranjul Pal
Tester: Deependra
Editorialist: Pranjul Pal

DIFFICULTY:

MEDIUM

PREREQUISITES:

Matrix Exponentiation

PROBLEM:

Calculate the total no. of infected people till N^{th} day \bmod 1000000007.
Given, every infected person till i^{th} day will infect x different non-infected persons on (i+1)^{th} day and y different non-infected persons on (i+2)^{th} day.

QUICK EXPLANATION:

Let’s call F(d) = total no.of infected persons till d^{th} day.
It can be proved that the total no. of infected persons till N^{th} day:
i.e. F(N)=(x+1)*F(N-1)+y*F(N-2)

EXPLANATION:

Let’s call F(d) = total no.of infected persons till d^{th} day.
It is given that spread of the virus started with 1 person i.e. F(1)=1 .
Since, this 1^{st} person with infect x non-infected persons on 2^{nd} day and y non-infected persons on 3^{rd} day.
So, total infected persons on 2^{nd} day i.e. F(2) = x*F(1)+F(1)
Let d be any day (d>=3):
Total no. infected persons till (d-1)^{th} day are F(d-1).
And total no. infected persons till (d-2)^{th} day are F(d-2).
So, F(d) can be calculated as F(d)=x*F(d-1)+y*F(d-2) +F(d-1).
Where x*F(d-1)+y*F(d-2) are the total no. of persons who are newly infected on d^{th} day and F(d-1) are already infected people till (d-1)^{th} day.
Obtained Formula: F(N)=(x+1)*F(N-1)+y*F(N-2)
Since the values are large, we need to calculate F(N) \bmod 1000000007 using Matrix Exponentiation .

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vll vector<ll>
#define vpll vector<pll>
#define vvll vector<vector<ll>>
#define sll stack<ll>
#define qll queue<ll>
#define mp make_pair
#define f first
#define s second
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define init(x,n,v) for(ll i=0;i<=n;i++) x[i]=v;
#define all(x) x.begin(),x.end()
#define pi 3.14159265358979323846
ll MOD = 1e9+7 , MAX = 1e18;
vvll mat;
void mul(vvll &a,vvll &b)
{
    ll i,j,k;
    vvll c={{0,0},{0,0}};
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            for(k=0;k<2;k++)
            {
                c[i][j]=(c[i][j]+(a[i][k]*b[k][j]%MOD))%MOD;
            }
        }
    }
    a=c;
}
void power(ll n)
{
    vvll res={{1,0},{0,1}};
    while(n)
    {
        if(n&1) mul(res,mat);
        mul(mat,mat);
        n/=2;
    }
    mat=res;
}
int main() 
{
#ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
#endif
    fast_io;
    Test
    {
        ll x,y,n,ans;
        cin>>x>>y>>n;
        if(n==1) ans=1;
        else if(n==2) ans=x+1;
        else
        {
            mat={{0,y},{1,x+1}};
            power(n-2);
            ans=(mat[0][1]+((x+1)*mat[1][1])%MOD)%MOD;
        }
        cout<<ans<<ln;
    }
    return 0;
}
5 Likes