P8735 蓝跳跳 题解

标签：le log 跳跳 题解 P8735 30 aligned pts 前缀

Statement

给出 \(k,p,L\)，数序列 \(a\)，满足如下条件：

• \(1\le a_i\le k\)
• \(\sum_i a_i=L\)
• \(\nexists i,a_i\ge p\land a_{i+1}\ge p\)

答案对 \(20201114\) 取模，\(p\le k\le 1000, L\le 10^{18}\).

Solution

30 pts

注意到可以 dp，记 \(f(i,0/1)\) 为凑出 \(i\) 的方案数，其中最后一个数是否 \(<p\).

\[ \begin{aligned} f(i,1)&=\sum_{1\le j<p} f(i-j,1)+f(i-j,0)\\ f(i,0)&=\sum_{p\le j\le k} f(i-j,1)\\ f(0,1)&=1 \end{aligned} \]

答案为 \(f(L,0)+f(L,1)\)，时间 \(O(kl)\)，预计得分 30 pts.

我做了个没什么用的前缀和优化：记 \(g(i,0/1)\) 为 \(f(i,0/1)\) 的前缀和，推式子可得

\[ \begin{aligned} g(i,0)&=g(i-1,0)+g(i-p,1)-g(i-k-1,1)\\ g(i,1)&=2g(i-1,1)+g(i-1,0)-g(i-p,1)-g(i-p,0)\\ g(0,1)&=1 \end{aligned} \]

答案为 \(g(L,0)-g(L-1,0)+g(L,1)-g(L-1,1)\)，时间 \(O(L)\)，预计得分 30 pts.

60 pts

用矩阵快速幂优化上述 dp，\(f\) 或 \(g\) 都可以，时间 \(O(k^3\log L)\)，带有 8 倍常数，预计得分 60 pts.

100 pts

直接线性递推即可，\(f\) 或 \(g\) 都可以，注意前 \(k+1\) 项需预处理，若 \(L\le k+1\) 就直接输出。

不用写任意模数乘法，直接暴力乘就行，这是 \(O(k^2\log L)\) 的，期望 100 pts.

这题可以稍微加强一下，以强迫你使用前缀和优化，并且写任意模数乘法。这是 \(O(k\log k\log L)\) 的。

因为目前各种板子都还没打，所以暂时还没有代码。

标签：le,log,跳跳,题解,P8735,30,aligned,pts,前缀
From： https://www.cnblogs.com/laijinyi/p/18364314