Given a string s and a number k. You need to tell count of distinct string of length k. s.t. k is a subset of s.
Eg 1. "aaabb" 2 => 4 (aa bb ab ba)
"aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc)
"abbcc" 2 => 8( same as #2 but aa can't be formed
I can create a dp of state index and mask where mask is of base 26 and rest is straightforward. Please help me in finding some combinatorics approach of solving it.
Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).
I have something want to say.
I have another dp state that dp[26][len] means the distinct string of length len where we have used which alpha. Transition is simple dp[i+1][len+c] <- dp[i][len] * C(len+c, c)
And I have another problem related with your problem. Here it is . The difference is that we must use all the char in the original string. Hope you enjoy solve this problem.
Could you please elaborate the transition a little? Particularly, what is c?
I guess, C is a binomial coefficient, that is $$$C(n, k) = C_n^k = \left(^n_k\right) = \frac{n!}{k!\cdot(n-k)!}$$$
Yes, the big C does represent the n choose k. But I meant what does len+c stand for?
Ah, yes, sorry. The answer is here.
Can you please elaborate how to solve the problem from CSES that you have given the link?
There are several ways to solve it.
First you can read the paper of Sequences with Adjacent Elements Unequal
Second you can use include-exclude principle with dp
Third you can read https://arxiv.org/pdf/1306.6232.pdf and related with generalized laguerre polynomials.
All of them may have connections with other methods
First thought that came to mind was lagurre , but it is not required here .
Also if you look behind the gamma function (for integration) in the blog or paper, its same as PIE
https://math.stackexchange.com/questions/2100546/arrangements-of-balls-from-a-bag
Here it is explained very nicely.also research paper link is given , but my point is given question is unrelated to this question or using this would be an overkill to solve simple problem.
https://www.codechef.com/problems/AMBALLS
Here is another task with editorial
We can solve the task given by OP in O(|C| * K *log K) as I mentioned below using EGF
Makes sense. small c is iterating variable for 0...freq[i] (assuming i is ith char in alphabets). Right?
right
i guess its classic application of E.G.F.
lets set of characters be $$$a_i,f_i $$$, here $$$f_i$$$ represents the frequency
your answer will be
$$$ [x^k] \prod_{i} (\sum_{j=0}^{f_i}\frac{x^j}{j!})$$$
here $$$\sum_{j=0}^{f_i}\frac{x^j}{j!} $$$ is generating function for character $$$a_i$$$ with frequenccy $$$f_i$$$
multiply by k! as we are using coeffiecient of $$$x^k$$$
like for first example answer is $$$2! \times [ \frac{1}{2!} + \frac{1}{1!} + \frac{1}{2!} ]$$$
which is equal to 4.
It's not making sense. Can you also write the example answer for case #2 and #3 ? That will help.
$$$2! \times [\frac{3}{2!0!} + \frac{3}{1!1!}]$$$
$$$2! \times [\frac{2}{2!0!} + \frac{3}{1!1!}]$$$
I am calculating this by hand you can easily multiply polynomial with fft convolution.
total complexity will be $$$ O(|C| * K * log(K))$$$
Solution is correct!. But I have no clue how it is correct. Any starting source to learn about generating functions ?
Basically when you have a certain combination of frequencies you have K!/(product of fi! for each frequency fi) ways to permute it. The polynomial described above does exactly this without the K!, so you just need to multiply K! to fix it. For getting started in this topic, I recommend solving this problem with generating function in mind:
https://codeforces.net/problemset/problem/712/D
It's my favorite basic but not trivial generating function problem. For something a bit harder:
https://codeforces.net/problemset/problem/451/E
Source for learning about it... idk, just understand how polynomials can be a powerful tool for combinatorics and solve problems with that in mind. For example, (1 + x)^n generates the n-th row in pascal's triangle, this kind of stuff.
Cool!. Thanks alot!!
This may help you:
https://www2.math.upenn.edu/~wilf/gfologyLinked2.pdf
link to japanese website
Google translate will work. After this read from https://codeforces.net/blog/entry/77468
I have a dp + combinatorics solution
let dp[i] denote the number of strings of length i, we have parsed till the jth alphabet. Lets say we take l number of jth alphabet
J is not used anywhere — are we considering sum(nCr for l = 1..J))? k is not used anywhere — answer is the same for every k?
No means actually it is dp[i][j] but you can compress the 2D DP into only dp[i] in knapsack right ? Also final answer is dp[k].
Still not getting it. If there is += dp[i-L]*... (let's use big L instead of little "l" since it's hard to tell them apart from "1") why are we taking difference between "number of strings of length i" and "L number of jth alphabet" in square brackets? So while k <= L we'll have dp[k] == 0 because there no dp[x] for x < 0 and nCr(i, l) = 0 for i < L?
Then for i = L + 1 dp[L+1] = dp[L] * nCr(L+1, L) = dp[L] * (L+1) — what is this — is this the number of new strings with 1 char added in every position? Nope, it won't work this way.
Not sure what you are not getting, maybe this code can help.
Yep, thanks! This makes it all clear. For every d[i] you count how many times you can add some letter L = 1..freq(letter) times, using previously calculated dp[i-L] for previous letters. This looks like O(k*length(s)) solution.