比赛心得 - NOI2024 省选 OIFC 模拟 8

· · 算法·理论

彩蛋：

\tt T1 排队

题目大意：一群人排队，男男间隔 a，男女间隔 b，女女间隔 c，男生打饭要 d 的单位时间，女生 e 的单位时间。

队列长 n 米，问可能的排队方式的排队时间总和是多少，对 10^9+7 取模。

显然看出一个 dp，可以先用 f_{0,i,0/1} 表示前 i 单位距离，最后一个人是 0 男 1 女的可能时间之和。

然后我们发现这样需要再用一个 f_{1,i,0/1} 来记录前面的人数。

状态转移方程：

f_{0,i,0}=f_{0,i-a,0}+f_{0,i-b,1}+d\times (f_{1,i-a,0}+f_{1,i-b,1})

即为前面男生，前面女生和前面男生打饭时间。

同理：

f_{0,i,1}=f_{0,i-c,1}+f_{0,i-b,0}+e\times (f_{1,i-c,1}+f_{1,i-b,0})

最后是：

f_{1,i,0}=f_{1,i-a,0}+f_{1,i-b,1} \\ f_{1,i,1}=f_{1,i-c,1}+f_{1,i-b,0}

这样就可以拿到 50 分了。

注意到注意力惊人我们的转移只和 i-a，i-b，i-c 有关。

那么我们考虑滚动数组优化？

忘记说了 \sout{a,b,c\leq 30}。

就可以只记录前 30 个数，就能不 RE 了。

注意到 n\leq 10^{18} 超时。

看来还是矩阵快速幂。

传奇乐子快速幂的 \sout{b} 没开 ll 然后出负数直接超时没救了。