Once ， more ， you open the door ， And you’re here in my heart.

$ordinary ~generating ~function$

We construct a OGF for the combination of $m$ stores.

Appearantly , the money is combinated by the sum of stores. And the choices are the Multiply principle of combination.

We let $F(x) = \prod_{k=1}^{m}\sum_{i=0}^{w_i}x^i$

Each polymial is a choice for a store.

The coefficient of $x^k$ is the $k$ dollors ‘ number of scheme.

The $n-m$ stores could be calculated by $plate ~insertion ~method$ , which is a classical method in math.

But a store could contribute 0 dollar.
We could create imagination balls…..(I do not understand actually)

Then we just need to expand the polymial , enumerates $t$ for the dolllars the $m$ stores contributed of $f_t$ , the remain $k-t$ dollars are from $n-m$ stores , use $plate ~insertion ~method$.

the answer is $\sum_{t=0}^{k}f_tC_{k-t+n-m-1}^{n-m-1}$

Time complexity is $O(m^4 + k)$

firstly I think it is $O(m^3)$ , then I got TLE…

Use $NTT$ could optimize it by $O(m^2logm + k)$

70pts Code:

# CF893F Subtree Minimum Query

## 题意翻译

x=(x′+lans)modn+1;

k=(k′+lans)modn;

BFS建权值主席树，二分AC