mistborn's blog

By mistborn, 14 months ago, In English

Say we are given the number of occurrences of each letter (lower case english alphabet). We have to find the number of all k length strings (unique) that can be formed using these letters (MOD 1e9 +7).

Example: a:2, b:1, c:1

k = 2

aa ab ac bc ca cb ba

Answer: 7

Constraints:

k <= 1e5

Total number of characters <= 1e5

I couldn't solve it. Any input is appreciated.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
14 months ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Right now I can only think of an ugly solution involves FFT.

The answer is the coefficient of $$$x^{k}$$$ in the result of $$$\prod_{i=1}^{n}(\sum_{j=0}^{min(a_i,k)}\frac{x^j}{j!})$$$ times $$$k!$$$ if $$$a_i$$$ denotes the max number of ith character we may have in this string.

Multiplication of two polynomials can be done in time $$$O(|degree \ of \ polynomial|\times log)$$$. So if we carefully multiply the two polynomials with the smallest degrees each time, this solution should be able to squeeze in the time limit.