Subtask 6
Considering promotion from Sub5.\(c_i \to c_{i,j}\) delegate\(i\) Steps to the first\(i+j\) The amount of step flow and then you get a formula that can be disassembled.
Then push seems to get better, and we continue to expand.
It's still a good idea to put\(\sum\limits_c\) Ignore it.
We set up a dialog box for all\(c_{i,j}\) The set formed by the occurrence subscripts of\(S_i\), then one can obtain such an equation.
Consider the outer layer\(\sum_{c}\) effects, it is clear that the first dimension differs\(c\) There is no interplay between them.
Start by multiplying the outer product\(\prod_{i=1}^{n}\) Expanded to several\(n\) sum of submonomials, and for each monomial, we consider\(c_{i,j}\) The constraint that the\(\sum_j c_{i,j} = a_i\)。
Using the law of multiplicative distribution, separately for each\(i\) dimensional\(c_{i,j}\) Perform a summation, and eventually we can wind up with a summation.
That doesn't seem like a very good thing to do, so we can construct a combinatorial meaning to simplify the question.
We use\(r_i\) means that for any legal\(j\)，\(c_{i,j}\) there are\(r_i\) A variable can be taken to a non\(0\) value, that is, the\(r_i=\min(n-i,k)+1\)。
Then we can model this:
There are numbered\(0,1,2,\dots,r_i-1\) (used form a nominal expression)\(r_i\) A box.
where the number falls in the category of\(S_i\) The box that holds the\(x\) Contributions from clubs\(x\)。
And the other boxes, no matter how many balls they put in, contribute to the\(1\)。
The contribution of a scenario is the product of the contributions of the individual boxes.
look forward to\(r_i\) Place any of the boxes\(a_i\) The sum of the contributions of the balls that don't make any difference.
It's still not good enough to do it, but at least you can build the generating function, can't you?
We can find out that we don't care\(S_i\) How much, exactly? That's all we care about.\(|S_i|\)。
We construct the generator function to do this, for the number in the\(S_i\) The boxes in the center, which are characterized by the placement of the\(x\) The contribution of the balls is\(x\)The generating function is\(\frac{x}{(1-x)^2}\)The contribution increases proportionally to the number of balls placed in the box.
The remaining boxes, which are characterized by the fact that no matter how many balls are put in them, the contribution is always\(1\), so its generating function is\(\frac{1}{1-x}\), the number of balls has no effect on the contribution, but we still allow the balls to be put in.
Combine these generating functions so that\(|S_i| = s_i\), then the total generating function is:
Simplify to get:
in order to get to\(r_i\) Boxes in which to place\(a_i\) contribution of a ball, we need to find the generating function\(G(x)\) center\(x^{a_i}\) The coefficients of the
That's equivalent:
treat (sb a certain way)\(\frac{1}{(1-x)^{s_i + r_i}}\) Unfold and get:
Substituting this expansion into\(G(x)\) Center:
In order to find\(x^{a_i}\) items that need to be met\(n + s_i = a_i\)The following is an example of the way in which the\(n = a_i - s_i\)。
Substitution gives\(x^{a_i}\) The coefficient of the term is:
It can be found that the results are only affected by\(S_i\) The effect of the above has already been mentioned, and we consider the\(s_i\) How it came to be.
It can be found that each\(i\) interacts with a set\(\max\{i-k,1\} \le j \le i\) It's a box of some kind.\(j\) happen to be contributing\(S_j\)。
each\(i\) It will only be contributed once in the corresponding interval.
everyone\(i\) The contribution can be made by multiple positions\(j \in (i,i+k)\) Contribution, which can be understood the other way around:
In fact, each\(s_i\) can be accessed from\(\{i, i+1, \dots, i+r_i-1\}\) Choose any of these positions to contribute.
carry out\(dp\) That's all, set\(f_{i,j}\) denote the presence of a suffix\(i\) there are\(j\) No contributions from any of the positions.\(s\) The sum of the weights of the
Just enumerate the transfers\(s\) Then the combinatorial number is computed with complexity\(O(n^3)\)