PROBLEM LINK:
Author & Editorialist : Mayuresh Patle
Tester : Uttkarsh Bawankar
DIFFICULTY:
EASY
PREREQUISITES:
Combinations, Counting, Modular Arithmetic, Modular Multiplicative Inverse.
PROBLEM:
You are given a string S containing lowercase English alphabets. You are also given a list of N names (which are strings too, containing only lowercase English alphabets). For each of these names, you’ve to calculate the total number of sub-sequences of string S which are anagrams of that name. Since this value could be very large, calculate this value modulo 998244535. This value is called as the score of the name.
Finally, print the name having maximum score, if there are more than one such names, then print the one which appeared first in the list. If all names have 0 score, then print “No Research This Month” (without quotes).
You’ve to do this for M testcases.
QUICK EXPLANATION
The score of each name is, \prod ^{S.count(c)}C_{name.count(c)} for each unique character c in name. Here, ^nC_r represents the total number of ways to select r objects out of available n objects.
EXPLANATION:
By definition, if a two strings are anagrams of each other, then the frequency of occurrences of each unique character in both of the string must be same. For example, if two string A and B are anagrams of each other, and the character c occurs exactly x times in A then, c must occurs exactly x times in B and vice-versa.
Let’s denote the count of occurrences of character c in string A by A.count(c). Now, we want to count the number of sub-sequences of S which satisfy the the above condition. Hence,
- We can first count and store the frequency of occurrences of each of the 26 alphabets in S.
- Then, for each name in the list, we will store the count of occurrences of each alphabet.
- Now, for each character c, we need to select exactly name.count(c) occurrences out of available S.count(c) occurrences in S. Total number of ways to select these for character c is ^{S.count(c)}C_{name.count(c)}.
- Hence, the final score will be the product of above expression for each c \in lowercase alphabets.
Some points to mention:
- The calculations might lead to overflow, hence, apply modulo operation after each step.
- After applying modulo operation, direct division will give wrong results, hence to calculate \frac{A}{B} \mod 998244353, you will have to calculate (A\ * B^{-1}) \mod 9982443535. Here, B^{-1} is the modular multiplicative inverse of B under modulo 998244353.
Time Complexity : O(|S| + N*(|name|+26*log_2(9982443535) )) for each testcase.
SOLUTIONS:
C++ Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vll;
const ll md=998244353, maxN=100001;
//function for modular exponentiation, returns (n^p) mod md
ll modex(ll n,ll p)
{
ll ans=1;
n%=md;
while(p)
{
if(p&1) ans=(ans*n)%md;
p>>=1;
n=(n*n)%md;
}
return ans;
}
ll fact[maxN]={1};
/*This function returns nCr mod md, i.e { n!/((n-r)!*r!) } mod md
nCr = no. of ways to select r objects out of n available objects
This function works in O(log2(md)) time*/
ll ncr(ll n,ll r)
{
if(n<r) return 0;
ll num=fact[n], den=(fact[n-r]*fact[r])%md;
ll inv=modex(den,md-2);
return (num*inv)%md;
}
int main()
{
//fast io
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll M,N,i,maxscore;
string S,name,result;
for(i=1;i<maxN;++i) fact[i]=(i*fact[i-1])%md; //calculate factorials
cin>>M;
while(M--)
{
cin>>S;
result="No Research This Month";
maxscore=0;
vll cntS(26);
for(char c:S) ++cntS[c-'a'];
cin>>N;
while(N--)
{
cin>>name;
ll score=1;
vll cntname(26);
for(char c:name) ++cntname[c-'a'];
for(i=0;score and i<26;++i) //calculate score
{
score=(score*ncr(cntS[i],cntname[i]))%md;
}
cout<<score<<"\n"; //print score
if(score>maxscore) //update result
{
maxscore=score;
result=name;
}
}
cout<<result<<"\n"; //print result
}
return 0;
}
Python 3 Solution
a='qwertyuiopasdfghjklzxcvbnm'
md=998244353
def ncr(n,r): #takes O(r*log2(md)) time
num,den=1,1
for i in range(r):
num=(num*(n-i))%md
den=(den*(i+1))%md
inv=pow(den,md-2,md)
return (num*inv)%md
for _ in range(int(input())):
s=input()
cnts={}
for c in a: cnts[c]=0
for c in s: cnts[c]+=1
maxscore,result=0,"No Research This Month"
for _ in range(int(input())):
name=input()
score=1
cnt={}
for c in a: cnt[c]=0
for c in name: cnt[c]+=1
for c in a:
score=(score*ncr(cnts[c],cnt[c]))%md
if score==0: break
print(score)
if score>maxscore:
result,maxscore=name,score
print(result)
