PROBLEM LINK:
Author: Manish
Tester: Neeraj
Editorialist: Sumit
DIFFICULTY:
EASY.
PREREQUISITES:
Math, Number theory.
PROBLEM:
Ganesh Gaitonde is a student of Mathematics at PEOPLE’s University. These days he is busy with his girlfriend Kuku. On the other hand, Kuku don’t like mathematics that much. One day, Kuku decided to find all the strings of length N (comprising only of characters from ‘0’ to ‘9’) having an odd number of 0’s. For Example: 103,012,000 are all strings of length 3 having an Odd number of 0’s. She asked Gaitonde to find number of such strings of for a given length of string modulo 1000000009 (10^9 + 9). Gaitonde being busy in organizing college fest asks for your help. Help Gaitonde impressing his girlfriend.
SOLUTIONS:
Setter's Solution
#include <iostream>
#define m 1000000009
#define ll long long int
using namespace std;
ll modularExponentiation(ll x,ll n,ll M)
{
if(n==0)
return 1;
else if(n%2 == 0) //n is even
return modularExponentiation((xx)%M,n/2,M);
else //n is odd
return (xmodularExponentiation((x*x)%M,(n-1)/2,M))%M;
}
int main()
{ ll n;
int t;
cin>>t;
while(t–)
{
cin>>n;
ll x=modularExponentiation(10,n,m);
ll y=modularExponentiation(8,n,m);
cout<<(((x-y+m)%m)*(modularExponentiation(2,m-2,m)))%m<<endl;
}
return 0;
}
Tester's Solution
indent whole code by 4 spaces
Editorialist's Solution
indent whole code by 4 spaces