Unique Strings
Contest: Educational Codeforces Round 164 (Rated for Div. 2)
Difficulty rating: 3100
Tags: combinatorics, dp, math

Let's say that two strings $$$a$$$ and $$$b$$$ are equal if you can get the string $$$b$$$ by cyclically shifting string $$$a$$$. For example, the strings 0100110 and 1100100 are equal, while 1010 and 1100 are not.

You are given a binary string $$$s$$$ of length $$$n$$$. Its first $$$c$$$ characters are 1-s, and its last $$$n - c$$$ characters are 0-s.

In one operation, you can replace one 0 with 1.

Calculate the number of unique strings you can get using no more than $$$k$$$ operations. Since the answer may be too large, print it modulo $$$10^9 + 7$$$.

Input format:
The first and only line contains three integers $$$n$$$, $$$c$$$ and $$$k$$$ ($$$1 \le n \le 3000$$$; $$$1 \le c \le n$$$; $$$0 \le k \le n - c$$$) — the length of string $$$s$$$, the length of prefix of 1-s and the maximum number of operations.

Output format:
Print the single integer — the number of unique strings you can achieve performing no more than $$$k$$$ operations, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only possible string is 1.

In the second test case, the possible strings are: 100, 110, and 111. String 101 is equal to 110, so we don't count it.

In the third test case, the possible strings are: 10000, 11000, 10100. String 10010 is equal to 10100, and 10001 is equal to 11000.

Example input:
1 1 0

Example output:
1

Example input:
3 1 2

Example output:
3

Editorial:
What's common in all strings we can get: each string has no more than $$$c + k$$$ ones and at least $$$c$$$ consecutive ones.
So let's loosen up our constraints a little and just calculate the number of strings with no more than $$$c + k$$$ ones and at least $$$c$$$ consecutive ones, i. e. this block of ones can be anywhere, can even start at the end and continue at the beginning. Let's name such strings as good strings.
Note that the number of unique good strings is exactly equal to the answer of the initial task, since we can shift each good string and make it start from the block of ones.
How to calculate the number of good strings? Using Burnside's lemma! Since the group of transformations is just a group of cyclic shifts, we can calculate the answer as following $$$$$$\mathrm{ans} = \frac{1}{n} \sum_{i=1}^{n}{\mathrm{FixedPoints}(i)}$$$$$$ where $$$\mathrm{FixedPoints(i)}$$$ is the number of fixed points, or the number of strings that won't change after a cyclical shift by $$$i$$$ characters.
Note that if the string doesn't change while shifting by $$$i$$$ characters, then it means that $$$s[p] = s[(p + i) \mod |s|]$$$ for all $$$p$$$. Further investigation reveals that all characters will be split into exactly $$$g = \gcd(i, n)$$$ groups and each group will contain exactly $$$\frac{n}{g}$$$ equal characters.
It means that if $$$\gcd(i, n) = \gcd(j, n)$$$ then $$$\mathrm{FixedPoints}(i) = \mathrm{FixedPoints}(j)$$$ since in both cases we'll get exactly the same group division. So, we can rewrite the answer as following: $$$$$$\mathrm{ans} = \frac{1}{n} \sum_{g | n}{cnt[g] \cdot \mathrm{FixedPoints}(g)}$$$$$$ where $$$cnt[g]$$$ is the number of cyclic shifts $$$i$$$ with $$$\gcd(i, n) = g$$$ and can be easily counted.
So, it's time to calculate $$$\mathrm{FixedPoints}(g)$$$ for some divisor $$$g$$$ of $$$n$$$. It's not hard to see that if $$$s[p] = s[(p + g) \mod |s|]$$$ then the first $$$g$$$ characters of $$$s$$$ will uniquely define the whole string $$$s$$$. So it's enough to work with only a prefix of length $$$g$$$, remembering that each character will be copied $$$\frac{n}{g}$$$ times.
Remember that a good string is a string with at most $$$c + k$$$ ones, and since each character will be copied $$$\frac{n}{g}$$$ times, we can place at most $$$on = \frac{(c + k) g}{n}$$$ ones in our prefix (or at least $$$zr = g - on$$$ zeroes).
Also, since a good string has $$$c$$$ consecutive ones, our prefix should also have $$$c$$$ consecutive ones, including the case where the ones go "cyclically" starting at the end of the prefix. In case if $$$c \ge g$$$ then the whole prefix should consist of ones, and it's either possible (if $$$c + k = n$$$) or impossible (if $$$c + k < n$$$).
In case $$$c < g$$$ we need to calculate the number of good prefixes that can be described as "the cyclic strings of length $$$g$$$ that has no more than $$$on$$$ ones and contains $$$c$$$ consecutive ones". Instead of good prefixes, let's calculate bad prefixes and subtract them from all possible prefixes.
All prefixes are just strings with at most $$$on$$$ ones and there are $$$all = \sum\limits_{i=0}^{on}{\binom{g}{i}}$$$ such strings.
Bad prefixes are cyclic strings with at most $$$on$$$ ones, where all blocks of ones have length less than $$$c$$$. In order to calculate bad prefixes, let's precalc the following dp: $$$d[z][l]$$$ is the number of strings of length $$$l$$$ with $$$z$$$ zeroes where all blocks of ones have length less than $$$c$$$ and the last character of the string is $$$0$$$.
Why did we use the number of zeroes in the state, and why did we add the last zero in $$$d[z][l]$$$? Because it will help us to calculate dp fast. $$$d[0][0] = 1$$$. Now, if we have value $$$d[z][l]$$$, we can add a block of $$$i$$$ ones ($$$0 \le i < c$$$) and zero to the end of the string and update the value in $$$d[z + 1][l + i + 1]$$$. Note that we are updating a segment of row $$$z + 1$$$ from $$$l + 1$$$ to $$$l + c$$$ with value $$$d[z][l]$$$ — we can do it in $$$O(1)$$$. So, we can precalc the whole dp in $$$O(n^2)$$$ time.
Now, it's time to calculate the number of bad strings: if we iterate over the length of the prefix of ones, length of the suffix of ones and the number of zeroes in between, we'll get $$$$$$bad = \sum_{p=0}^{c - 1}\sum_{s = 0}^{c - p - 1}\sum_{z = zr - 1}^{g - p - s - 1}{d[z][g - p - s - 1]}$$$$$$ where $$$p$$$ is the number of ones on prefix, $$$s$$$ is the number of ones on suffix, and $$$z$$$ is the number of zeroes in the "middle part". Since each bad string will look like "($$$p$$$ ones)–0–(middle part ending at 0)–($$$s$$$ ones)", you can place in the middle part at least $$$zr - 1$$$ zeroes and at most $$$g - p - 1 - s$$$ zeroes.
If we play a little with the sum, we can simplify it in the following way: $$$$$$bad = \sum_{p = 0}^{c - 1}\sum_{z = \max(0, zr - 1)}^{g - p - 1}{\mathrm{sumD}(z, g - c, g - p - 1)}$$$$$$ where $$$\mathrm{sumD}(z, g - c, g - p - 1)$$$ is the sum of dp on the row $$$z$$$ from $$$g - c$$$ to $$$g - p - 1$$$, and you can take it in $$$O(1)$$$ if you precalc prefix sums of dp.
Good prefixes are just $$$all - bad$$$ and since $$$bad$$$ can be calculated in $$$O(g^2)$$$, the total complexity of $$$\mathrm{FixedPoints}(g)$$$ is $$$O(g^2)$$$.
The resulting complexity is $$$O(n^2) + \sum\limits_{g|n}{O(g^2)}$$$ that looks like just $$$O(n^2)$$$.