CF865G tutorial

Now all the tutorial I can find is to use GF and the poly multiplication. I can provide a slower but more beginner-friendly solution.

Hint

How would you naively count the number of ways to get exactly​ $$$K$$$ chocolates in a basket?

There is a classic technique to optimize them.

Note $$$c_i$$$ is small but $$$p_i$$$ is big.

Note $$$F$$$ and $$$B$$$ are small.

Step 1

A straightforward way to compute ways to get exactly $$$K$$$ chocolates in a basket is to write dp.

Let $$$f[i]$$$ be the number of ways to get exactly $$$i$$$ chocolates.

Let $$$b[i]$$$ the number of boxes whose length is $$$i$$$.

We can enumerate the last size of boxes to get a transition.

$$$f[i]=\sum_j b[j]f[i-j]$$$

Use matrix exponentiation​ to speed up th procudure if the maximum chocolate count we need is not too large.

Step 2

Note that $$$p_j\leq 10^9,n\leq 10^18$$$ and we cannot use the previous method to compute.

We change the perspective: instead of tracking total petals, we track the number of bouquets. Let $$$g[i][j]$$$ be the number of ways to collect $$$i$$$ bonquets already but $$$j$$$ extra chocolates. Then we can transition it by enumerate the next flower and use the previous $$$f$$$.

And we can also speed up it by matrix exponentiation​.

Step 3

But this get TLE. Why?

1. use % less
2. add constant optimize everywhere ,especially matrix exponentiation​
3. use #pragma

code

目前我能找到的所有题解都使用了生成函数（GF）和多项式乘法。我将提供一个虽然较慢，但对初学者更友好的解法。

Hints

如何用朴素的方法计算**恰好**得到 $$$K$$$ 块巧克力的方案数？

这里有一个经典的优化技巧。

注意：$c_i$ 很小，但 $$$p_i$$$ 很大。 注意 $$$F$$$ 和 $$$B$$$ 也很小。

Step 1

计算恰好得到 $$$K$$$ 块巧克力方案数的一个直接方法是动态规划（DP）。

设 $$$f[i]$$$ 为恰好得到 $$$i$$$ 块巧克力的方案数。

设 $$$b[i]$$$ 为长度为 $$$i$$$ 的盒子的数量。

我们可以枚举最后一个盒子的尺寸来进行状态转移。

$$$f[i]=\sum_j b[j]f[i-j]$$$

如果我们需要计算的最大巧克力数量不是特别大，可以使用矩阵快速幂来加速这个过程。

Step 2

注意 $p_j\leq 10^9, n\leq 10^{18}$，我们不能直接使用之前的方法计算。

我们转换一下思路：不再追踪总花瓣数，而是追踪花束的数量。设 $$$g[i][j]$$$ 为已经收集了 $$$i$$$ 个花束，但还额外剩下 $$$j$$$ 块巧克力的方案数。然后，我们可以通过枚举下一朵花，并利用之前计算好的 $$$f$$$ 来进行状态转移。

同样，我们可以用矩阵快速幂来加速。

Step 3

但这可能会超时（TLE）。为什么？

1. 减少取模运算（%）的使用
2. 在所有地方添加常量优化，特别是矩阵快速幂部分
3. 使用 #pragma 编译优化指令

code