CODEKARO - Editorial

PROBLEM LINK:

Contest
Practice

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

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