Solution:P5615([MtOI2019] 时间跳跃)

Argon_Cube · 2023-11-18 20:45:24 · 题解

如何判定能不能组成多边形其它题解说过了，就是除了最长边以外的其它边长度之和大于最长边。

那么我们枚举最长边，设它长度为 n。我们发现选一些小于 n 的数使得和大于 n 是不好做的，那么正难则反，我们选一些数使得它们的和小于等于 n。

这时我们就可以计数了。我们设 g_n 是所有选取正整数数使得和不超过 n 的方案中选出来数的个数的和，f_i 是选取正整数数使得和不超过 n 的方案数。

先特判 n=1，在确定最长边 n 的情况下，我们先忽略 n 带来的贡献，那么选取剩下的数造成的总贡献显然是 (n-1)2^{n-2}，其中不合法的贡献是 g_n-1（减的 1 是只选一个 n 的方案）。考虑 n 带来的贡献，它在每个合法方案中都会带来一次贡献，显然合法方案数是 2^{n-1}-(f_n-1)（减的 1 同样是只选一个 n 的方案）。

这样最长边为 n 时总贡献就是 (n+1)2^{n-2}-g_n-f_n+2。

怎么 \Theta(n^2) 地求出 f,g 其它题解说的很清楚了，但是显然 f 就是互异分拆数的前缀和，g 就是整数拆分中所有方案大小之和的前缀和。

换句话说，我们只需要求出 \mathrm A000009 然后做前缀和就是 f，\mathrm A015723 做前缀和就是 g。

然后它们的生成函数满足一个神奇的公式：

\mathrm A048272 显然可以 \Theta(n\log n) 求吧，\mathrm A000009 显然可以套路的用计算分拆数的 \exp\ln 方法（见 P5824 和 P4389），也可以 \Theta(n\log n) 求（但是模数是 10^9+7 所以你要写一个任意模数 \ln 和 \exp）。然后卷起来就是 \mathrm A015723。

于是我们就以 \Theta(n\log n) 的时间复杂度解决了这题。