CF 1580F¶

Description¶

给出$n,m$，求满足下列条件的序列$\{a_0,a_1,\dots,a_{n-1}\}$个数：

$\bullet$ $\forall i\in[0,n),a_i\in[0,m)$

$\bullet$ $\forall i\in[0,n), a_i+a_{(i+1)\%n}<m$

$n\le50000,m\le10^9,8000ms$

Solution¶

将$<\lceil\frac{m}{2}\rceil$的数称为小数，$\ge\lceil\frac{m}{2}\rceil$的数称为大数。

则若两个相邻的数均为小数，它们的和一定$<m$，大数相邻必然不合法。

考虑将环在每两个相邻的小数间切断，会得到若干段形如“小大小$\cdots$小大小”的段，且段与段之间互不影响，只要能求出每种长度的段的个数，则可以借助生成函数算出合法的环的个数。当然，环的长度为偶数时可能没有相邻的小数，现在暂时不考虑。

现对$m$的两类合法段作出定义如下：

一类合法段：若$i$为偶数，则$a_i$为小数；否则$a_i$为大数。

二类合法段：$\forall i\in[0,n-1), a_i+a_{i+1}<m$，与题目要求的序列类似，但对序列首尾没有要求。

我们发现，将$m$的一类合法段中的每个大数减去$\lceil\frac{m}{2}\rceil$，可以得到一个$\lfloor\frac{m}{2}\rfloor$的二类合法段，实际上，它们是一一对应的。这样，我们就可每次把$m$减半，转化为规模更小的子问题。现在我们可以通过$\lfloor\frac{m}{2}\rfloor$的二类合法段求$m$的一类合法段，问题是如何通过$m$的一类合法段求$m$的二类合法段。

我们又可以发现，大部分二类合法段可以这样划分：大小大小$\dots$大小|若干个奇数一类合法段|小大$\dots$小大小大。即头为某个偶数一类合法段反过来，尾为某个偶数一类合法段（头尾长度都可能为$0$），中间是若干个奇数一类合法段（也可能为$0$个）。这样唯一遗漏的情况是形如大小大小大这样头尾都是大，中间大小交替的情况，令这些情况中的所有大数减去$\lceil\frac{m}{2}\rceil$，小数加上$\lceil\frac{m}{2}\rceil$，则发现其与相同长度的一类合法段是一一对应的。设奇数长度的一类合法段生成函数为$A$，偶数长度的二类合法段生成函数为$B$，则二类合法段的生成函数$C$为 $$ C=\frac{B^2}{1-A}+A $$ 至此，问题只剩下如何通过这些合法段的个数求合法环的个数。若$a_0$和$a_{n-1}$在同一个奇数长度的一类合法段中，可以枚举该段长度进行计数；否则，若$n$为奇数，则$a_0$和$a_{n-1}$必然均为小数，这部分方案数为若干个奇数一类合法段拼起来的方案数；若$n$为偶数，除了包括$n$为奇数时的情况，还包括了$n$个数组成一个一类合法段的情况，这部分方案数为$\lceil\frac{m}{2}\rceil$时的合法环个数乘二，即每种方案对应着选择让所有偶数位置的数加上$\lceil\frac{m}{2}\rceil$或者让所有奇数位置的数加上$\lceil\frac{m}{2}\rceil$两种方案。至此，本题解决，时间复杂度$\mathcal{O}(n\log n\log m)$。