LibreOJ 6731 「2019 山东一轮集训 Day3」小孩召开法

令 ak(n) 为答案。
为了导出递推式，我们考虑一下原问题。

注意到必然至少存在一个最长交替子序列经过最大值 n，于是考虑枚举 n 的位置为 i。
然后首先要从 n−1 个数中选择 i−1 个放到左边。
接下来考虑两边分配的交替子序列长度。枚举 2r+1+s=k，那么左边可以有 2r 或 2r+1 的交替子序列（因为 n 可以替换掉 2r+1 处的），右边可以有 s 的交替子序列。
因此 fk(n)=n∑i=1(n−1i−1)∑2r+s=k−1(f2r(i−1)+f2r+1(i−1))fs(n−i)

设 BGF F(x,t)=∑fk(n)xnn!tk，F0(x,t)=∑f2k(n)xnn!t2k，F1(x,t)=∑f2k+1(n)xnn!t2k+1。
那么根据如上递推式，我们有 ∂F∂x=(tF0+F1)F∂F0∂x=(tF0+F1)F1∂F1∂x=(tF0+F1)F2

然后注意到 ∂(F20−F21)∂x=∂F20∂x−∂F21∂x=0

这样对于 F20−F21，我们只需要对照常数。而根据定义仅有 F0 在 x0 处有 1，因此 F20−F21=1=(12(F(x,t)+F(x,−t)))2−(12(F(x,t)−F(x,−t))2=F(x,t)F(x,−t)

则 ∂F∂x=(tF0+F1)F=12((t+1)F+(t−1)F−1)F∂F((t+1)F+(t−1)F−1)F=∂x2

设 G=F1−t，则 F=(1−t)G。代入得 ∂G(1−t2)G2−1=∂x2

令 α=√1−t2，我们作部分分式分解，就有 ∂(αG)(1αG−1−1αG+1)=α∂xlnαG−1αG+1=αx+C′αG−1αG+1=eαx+C′=eαxCG=1+Ceαxα(1−Ceαx)

其中 C′,C=eC′ 关于 x 都是常数。
然后注意到 B(0,t)=11−t，因此 C=α1−t−1α1−t+1=1−αt

因此 G=1α(21−Ceαx−1)=1α(21−1−αteαx−1)

我们显然可以不管 [x0]，接下来尝试提取其系数 2α(1−1−αteαx)−1=2α∑r(1−αteαx)r=2α∑r(1−αt)r∑s(rαx)ss!=2∑rt−r∑s(rx)ss!(1−α)rαs−1

在出题人给出的标准做法中，这里凑出了一个有趣的形式，然后利用具体数学中提到的恒等式来辅助推导，但未免太过匪夷所思，这里展示一种更暴力却也更自然的做法（虽然最后推得的结果形式也不尽相同）。

我们想要展开 (1−√1−t2)r(1−t2)(s−1)/2

不妨作换元，令 4x=t2，则 t24=x，且原式变为 (1−√1−4x)r(1−4x)(s−1)/2

令 F 满足二叉树方程 F=x(1+F)2 就有熟知结论 F=1−2x−√1−4x2x,x=F(1+F)2

我们把原式整理成复合形式 (1−√1−4x)r(1−4x)(s−1)/2=(2x(1+F))r(1−2x−2xF)s−1=2rxr(1+F)r(1−2x(1+F))s−1=2rFr(1−F)s−1(1+F)−r−s+1

然后使用另类拉格朗日反演提取系数 [xn]Fr(1−F)r−1(1+F)−r−s+1=[xn]xr(1−x)r−1(1+x)−r−s+11−x(1+x)3(1+x)2n+2=[xn]xr(1−x)r(1+x)2n−r−s=∑i(−1)i(ri)(2n−r−sn−r−i)

代回到原式，就有 =2∑rt−r∑s(rx)ss!2r∑l(t24)l∑i(−1)i(si)(2l−r−sl−r−i)=2∑rt−r∑s(rx)ss!2r∑u(t24)r+u∑i(−1)i(si)(r+2u−su−i)=∑r,s,u21−r−2utr+2u(rx)ss!∑i(−1)i(si)(r+2u−su−i)

则令 n=s,k=r+2u，便知 gk(n)=21−k∑2i+r≤k,r≡k(mod2)rn(−1)i(ni)(k−nk−r2−i)

枚举 r，则需要计算形如 ft=∑i(−1)i(ni)(−st−i)

的数列。
考虑其生成函数，显然其为 F(x)=(1+x)−s(1−x)n

求导 F′=−sF1+x−nF1−x

即 tft=−(n+s)ft−1+(s−n+t−2)ft−2

时间复杂度 O(klogkn)。

感觉这题有意思的地方主要在于最前面的 DP 和微分方程部分，以及后面的提取系数部分。
由于这个题很明显是先想题意再想做法的，所以想复刻这种做法的题目还是比较无从下手（好像暴露了啥

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int K = 1e6;
const int mod = 998244353;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
long long n;
int k;
int ans;
int inv[K + 5];
int vis[K + 5],cnt,prime[K + 5],pw[K + 5];
int f[K + 5];
int get(long long n,int k)
{
    if(k <= 0)
        return 0;
    int ret = 0;
    int s = (n - k) % mod;
    f[0] = 1;
    for(register int t = 1;t <= (k >> 1);++t)
        f[t] = ((2 * mod - n % mod - s) % mod * f[t - 1] + (s + t - n % mod - 2 + mod) % mod * (t >= 2 ? f[t - 2] : 0)) % mod,
        f[t] = (long long)inv[t] * f[t] % mod;
    for(register int r = k;r >= 0;r -= 2)
        ret = (ret + (long long)pw[r] * f[k - r >> 1]) % mod;
    ret = (long long)ret * fpow(2,(mod - k) % (mod - 1)) % mod;
    return ret;
}
int main()
{
    scanf("%lld%d",&n,&k);
    pw[1] = 1;
    for(register int i = 2;i <= k;++i)
    {
        if(!vis[i])
            pw[i] = fpow(i,n % (mod - 1));
        for(register int j = 1;j <= cnt && i * prime[j] <= k;++j)
        {
            vis[i * prime[j]] = 1,pw[i * prime[j]] = (long long)pw[i] * pw[prime[j]] % mod;
            if(!(i % prime[j]))
                break;
        }
    }
    inv[1] = 1;
    for(register int i = 2;i <= (k >> 1);++i)
        inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
    ans = (get(n,k) - get(n,k - 1) + mod) % mod;
    printf("%d\n",ans);
}