# CODEKARO - Editorial

Author : Mayuresh Patle
Testers : Jaymeet Mehta, Smit Mandavia, Taranpreet Singh
Editorialist : Mayuresh Patle

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;
}


Can anybody tell me how for an odd number of places we are multiplying it with 52 ??
In middle, we can have ((52-2*k)+k) because for k alphabet both capital and small alphabet will be counted as one … isn’t it?

No, if m and M are similar then Mam, and mam are palindromes, but still these are two different strings, similarly aMa and ama will be 2 different strings.

Can anyone tell me for 0<=K <=26 how will be denominator= 52 ^L - (L mod 2) ?

As mentioned in the editorial:

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.

And,

the total number of strings of length L will be 52^L

Let N = (52 + 2*K)^{\lfloor \frac{L}{2} \rfloor}, i.e. the number of plaindromes when L is even.

Now, when L is even the fraction will be:

\frac{N}{52^L}

And, when L is odd the fraction will be:

\frac{52*N}{52^L} = \frac{N}{52^{L-1}}

Hence, the power of 52 is L for even L and L-1 for odd L, in the denominator.
In other words, you have to subtract 0 from L if L is even, else subtract 1 if L is odd, which can be generalized to subtracting L \mod 2.

1 Like

ok got it thanks