PROBLEM LINK:
Author : Mayuresh Patle
Testers : Jaymeet Mehta, Smit Mandavia, Taranpreet Singh
Editorialist : Mayuresh Patle
DIFFICULTY:
EASY
PREREQUISITES:
Basic Combinatorics, Probability, Modular Multiplicative Inverse
PROBLEM:
Given the length L_i of string which may contain both uppercase and lowercase English alphabets, find the probability that this string will be a palindrome, under the condition that for exactly K (0 \leq K \leq 26) alphabets, their uppercase and lowercase representations are treated to be similar.
This probability can be represented as P/Q where P and Q are integers. Thus, print the result as P.Q^{-1} \mod 10^9+7, where Q^{−1} denotes the modular multiplicative inverse of Q(modulo (10^9+7)).
EXPLANATION:
Considering all 52 (uppercase and lowercase) characters, it can be proved that the total number of strings of length L will be 52^L, since each one of the L positions in the string can be occupied by any of the available 52 characters.
For any string S of length L to be a palindrome, S[i]=S[L-i] must be satisfied, \forall i \in [1,L]. Thus for every pair of indices (i,L-i), we need similar characters at both indices.
- Here, the order of indices in pairs do not matter, i.e. (i,L-i) will be same as (L-i,i).
- Also, for odd L this condition will always hold true for center element ( i.e. for (\frac{L}{2}, \frac{L}{2})).
Thus we have total \lfloor \frac{L}{2} \rfloor such pairs to deal with.
For K=0:
If K=0, then for each pair we need to have exactly same character at both the indices.
Since we can choose any of the 52 characters for any of the {\lfloor\frac{L}{2}\rfloor} pairs, total number of palindromes will be 52^ {\lfloor\frac{L}{2}\rfloor} in this case.
Hence, in this case, the numerator will be 52^ {\lfloor\frac{L}{2}\rfloor} and denominator will be 52^L, after performing division ,we get P = 1 and Q = 52^{\lceil\frac{L}{2}\rceil}
For 0 \leq K \leq 26:
In this case, each pair can be:
- (uppercase,uppercase) for any character, i.e. total 26 pairs.
- (lowercase,lowercase) for any character, i.e. total 26 pairs.
- (uppercase,lowercase) for any of the K characters, i.e. total K pairs.
- (lowercase,uppercase) for any of the K characters, i.e. total K pairs.
Considering all these possibilities, we have total (26 + 26 + K + K) = (52+2*K) possibilities for every single pair.
Thus, total number of palindromes will be:
- (52 + 2*K)^{\lfloor \frac{L}{2} \rfloor} if L is even.
- 52*(52 + 2*K)^{\lfloor \frac{L}{2} \rfloor} if L is odd, since we can have any of the 52 characters at the center.
Hence, numerator=(52 + 2*K)^{\lfloor \frac{L}{2} \rfloor} and denominator=52^{L - (L \mod 2)}, since 52 will be canceled out from numerator and denominator for odd L.
Since complete division is concerned, the result will be same even if P and Q are not co-primes. Thus, P=numerator and Q=denominator.
Since m = (10^9+7) is prime, we can use Fermats’s little theorem to calculate P . Q^{-1} \mod m.
Hence, Q^{-1} \mod m \equiv Q^{m-2} \mod m.
Therefore, the required probability will be (P * (Q ^ {m-2} \mod m)) \mod m.
Time Complexity : O( \log m) for each string.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define modinv(n,m) modex(n,m-2,m)
#define moddiv(n,d,m) (n*modinv(d,m))%m
const ll mod=1e9+7;
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,k,l,nr,dr;
cin>>T;
while(T--)
{
cin>>n>>k;
k<<=1;
while(n--)
{
cin>>l;
nr=modex(52+k,l>>1,mod);
dr=modex(52,l-(l&1),mod);
cout<<moddiv(nr,dr,mod)<<endl;
}
}
return 0;
}