题解 CF1580F Problems for Codeforces

· · 题解

题意

求长度为 n，相邻两个数（包括 1 和 n）之和 <m 的序列个数，对 998244353 取模，n \leq 5\times 10^4, m \leq 10^9。

题解

为方便表述，下文将用大写字母表示小写字母的 OGF，用 m/2 替代 \left\lfloor\dfrac{m}{2}\right\rfloor。

将 < \left\lceil\dfrac{m}{2}\right\rceil 的数叫做「小数」（用 \tt S 表示），\ge \left\lceil\dfrac{m}{2}\right\rceil 的数叫做「大数」（用 \tt B 表示），那这个环有两种情况：

  1. 被分成若干个 \tt{SBS\dots BS}（以 \tt S 开头， 以 \tt S 结尾，且 \tt SB 交替）的「奇段」；
  2. 整个环是 \tt SB 交替的。

Part 1

先考虑第一种情况的计数，我们断环为链，统计由奇段拼成的链的个数。不妨长度为 i 的奇段有 a_i 种方案，用若干奇段拼成长度为 i 的链有 t_i 种方案，则考虑其 OGF 有 T(x) = \dfrac{1}{1-A(x)}。分两种讨论：

故 res=t_n + \sum (i-1)t_{n-i}a_i，如何求 a？

称相邻两个数（不含 1 和 n）之和 <k 的序列为「k 序列」，有个牛逼转化：将奇段的所有大数减去 \left\lceil\dfrac{m}{2}\right\rceil 后，与所有的「m/2 序列」一一对应。不妨加一维 m，f_{m,i} 表示长为 i 的「m 序列」个数，a_{m,i} 同理，则有 a_{m,i} = f_{m/2,i}（注意对 a_{m,1} 并不适用），考虑求 f。

序列和环的不同点在于，序列的首尾不一定是奇段：可能是开头形如 \tt{BSB\dots BS}，中间一堆奇段，结尾形如 \tt{SBS\dots SB} 的形式。我们把 \tt{BSB\dots BS} 这种 \tt B 开头 \tt S 结尾，且 \tt BS 交替的段叫「偶段」（特别地，偶段可以为空），则序列的组成一定是 偶段 + 若干奇段 + 反的偶段，这让我们想到 GF：不妨设长度为 i 的偶段有 b_i 种方案，则 F(x) = \dfrac{B(x)^2}{1-A(x)}。但它是错误的，漏掉了一种情况：\tt BSB\dots SB。对于这种情况，容易发现和奇段一一对应，所以 F(x) = A(x)+\dfrac{B(x)^2}{1-A(x)}。同样的，上面的牛逼转化对于偶段仍然适用，也就是 b_{m,i} = f_{m/2,i}，这样的话可以用 F_{m/2} 推得 A_m,B_m，然后推得 F_m。

因为 m 每次减半，所以 F_i 只有 O(\log m) 个，复杂度是 O(n \log n \log m)。

Part 2

整个环是 \tt SB 交替的，这种情况只会出现在 n 为偶数时。记 g_k 表示长度为 n 且 m=k 时 \tt SB 交替的序列个数，ans_k 表示 m=k 时的答案。

我们发现将所有大数减去 \left\lceil\dfrac{m}{2}\right\rceil 后，就是一个规模为 m/2 的子问题，所以考虑用 ans_{m/2} 还原回 g_k 的方式：奇数位 +\left\lceil\dfrac{m}{2}\right\rceil，或偶数位 +\left\lceil\dfrac{m}{2}\right\rceil，故 g_m = 2\cdot ans_{m/2}。结合 Part 1 求得的答案 res_m 可以得到 ans_m=res_m + g_m，就以 O(n \log n \log m) 的复杂度完成了这道题。

int n,m,rs;
poly solve(int m){
    if(!m)return poly(n+1,1);
    poly F=solve(m/2),A(n+1),B(n+1,1);
    FOR(i,1,n)(i&1?A[i]:B[i])=F[i];
    A[1]=(m+1)/2;
    poly I=Inv(poly(1,1)-A);
    F=A+B*B*I,rs=n&1?I[n]:(2ll*rs+I[n])%mod;
    FOR(i,3,n)rs=(rs+(i-1ll)*I[n-i]%mod*A[i])%mod;
    return F.fit(n+1);
}
signed main(){
    scanf("%d%d",&n,&m);
    solve(m),printf("%d",rs);
    return 0;
}