令 \(a_k(n)\) 为答案。
为了导出递推式，我们考虑一下原问题。
注意到必然至少存在一个最长交替子序列经过最大值 \(n\)，于是考虑枚举 \(n\) 的位置为 \(i\)。
然后首先要从 \(n-1\) 个数中选择 \(i-1\) 个放到左边。
接下来考虑两边分配的交替子序列长度。枚举 \(2r+1+s=k\)，那么左边可以有 \(2r\) 或 \(2r+1\) 的交替子序列（因为 \(n\) 可以替换掉 \(2r+1\) 处的），右边可以有 \(s\) 的交替子序列。
因此 \[
f_k(n) = \sum\limits_{i=1}^n \binom{n-1}{i-1} \sum\limits_{2r+s=k-1} (f_{2r}(i-1) + f_{2r+1}(i-1))f_s(n-i)
\]
设 BGF \(F(x,t) = \sum f_k(n) \frac{x^n}{n!} t^k\)，\(F_0(x,t) = \sum f_{2k}(n) \frac{x^n}{n!} t^{2k}\)，\(F_1(x,t) = \sum f_{2k+1}(n) \frac{x^n}{n!} t^{2k+1}\)。
那么根据如上递推式，我们有 \[
\begin{aligned}
\frac{\partial F}{\partial x} &= (tF_0 + F_1) F \\
\frac{\partial F_0}{\partial x} &= (tF_0 + F_1) F_1 \\
\frac{\partial F_1}{\partial x} &= (tF_0 + F_1) F_2
\end{aligned}
\]
然后注意到 \[ \begin{aligned} \frac{\partial(F_0^2-F_1^2)}{\partial x} &= \frac{\partial F_0^2}{\partial x} - \frac{\partial F_1^2}{\partial x} \\ &= 0 \end{aligned} \]
这样对于 \(F_0^2 - F_1^2\)，我们只需要对照常数。而根据定义仅有 \(F_0\) 在 \(x^0\) 处有 \(1\)，因此 \[ \begin{aligned} &\quad \; F_0^2 - F_1^2 \\ &= 1 \\ &= \left(\frac12(F(x,t)+F(x,-t))\right)^2 - \left(\frac12(F(x,t)-F(x,-t)\right)^2 \\ &= F(x,t) F(x,-t) \end{aligned} \]
则 \[ \begin{aligned} \frac{\partial F}{\partial x} &= (tF_0 + F_1) F \\ &= \frac12 ((t+1)F+(t-1)F^{-1}) F \\ \frac{\partial F}{((t+1)F+(t-1)F^{-1})F} &= \frac{\partial x}2 \end{aligned} \]
设 \(G = \frac F{1-t}\)，则 \(F = (1-t)G\)。代入得 \[ \frac{\partial G}{(1-t^2)G^2-1} = \frac{\partial x}2 \]
令 \(\alpha = \sqrt{1-t^2}\)，我们作部分分式分解，就有 \[ \begin{aligned} \partial (\alpha G) \left(\frac1{\alpha G-1} - \frac1{\alpha G+1}\right) &= \alpha \partial x \\ \ln \frac{\alpha G - 1}{\alpha G + 1} &= \alpha x + C' \\ \frac{\alpha G - 1}{\alpha G + 1} &= {\rm e}^{\alpha x+C'} \\ &= {\rm e}^{\alpha x} C \\ G &= \frac{ 1+C{\rm e}^{\alpha x} }{\alpha(1-C{\rm e}^{\alpha x})} \end{aligned} \]
其中 \(C',C={\rm e}^{C'}\) 关于 \(x\) 都是常数。
然后注意到 \(B(0,t) = \frac1{1-t}\)，因此 \[
C = \frac{\frac{\alpha}{1-t}-1}{\frac{\alpha}{1-t}+1} = \frac{1-\alpha}t
\]
因此 \[ G = \frac1{\alpha} \left(\frac2{ 1-C{\rm e}^{\alpha x} }-1\right) = \frac1{\alpha} \left(\frac2{ 1-\frac{1-\alpha}t{\rm e}^{\alpha x} }-1\right) \]
我们显然可以不管 \([x^0]\)，接下来尝试提取其系数 \[ \begin{aligned} &\quad\; \frac 2{\alpha} \left(1-\frac{1-\alpha}t {\rm e}^{\alpha x}\right)^{-1} \\ &= \frac 2{\alpha} \sum\limits_r \left(\frac{1-\alpha}t {\rm e}^{\alpha x} \right)^r \\ &= \frac 2{\alpha} \sum\limits_r \left(\frac{1-\alpha}t\right)^r \sum\limits_{s} \frac{(r\alpha x)^s}{s!} \\ &= 2 \sum\limits_r t^{-r} \sum\limits_{s} \frac{(rx)^s}{s!} (1-\alpha)^r \alpha^{s-1} \\ \end{aligned} \]
在出题人给出的标准做法中，这里凑出了一个有趣的形式，然后利用具体数学中提到的恒等式来辅助推导，但未免太过匪夷所思，这里展示一种更暴力却也更自然的做法（虽然最后推得的结果形式也不尽相同）。
我们想要展开 \[ (1-\sqrt{1-t^2})^r (1-t^2)^{(s-1)/2} \]
不妨作换元，令 \(4x=t^2\)，则 \(\frac{t^2}4=x\)，且原式变为 \[ (1-\sqrt{1-4x})^r (1-4x)^{(s-1)/2} \]
令 \(F\) 满足二叉树方程 \(F = x(1+F)^2\) 就有熟知结论 \[ F = \frac{ 1-2x-\sqrt{1-4x} }{2x},\quad x = \frac{F}{(1+F)^2} \]
我们把原式整理成复合形式 \[ \begin{aligned} (1-\sqrt{1-4x})^r (1-4x)^{(s-1)/2} &= (2x(1+F))^r (1-2x-2xF)^{s-1} \\ &= 2^r x^r (1+F)^r (1-2x(1+F))^{s-1} \\ &= 2^rF^r (1-F)^{s-1} (1+F)^{-r-s+1} \end{aligned} \]
然后使用另类拉格朗日反演提取系数 \[ \begin{aligned}[] [x^n] F^r (1-F)^{r-1} (1+F)^{-r-s+1} &= [x^n] x^r (1-x)^{r-1} (1+x)^{-r-s+1} \frac{1-x}{(1+x)^3} (1+x)^{2n+2} \\ &= [x^n] x^r (1-x)^r (1+x)^{2n-r-s} \\ &= \sum\limits_i (-1)^i \binom ri \binom{2n-r-s}{n-r-i} \end{aligned} \]
代回到原式，就有 \[ \begin{aligned} &= 2 \sum\limits_r t^{-r} \sum\limits_{s} \frac{(rx)^s}{s!} 2^r \sum\limits_l \left(\frac{t^2}4\right)^l \sum\limits_i (-1)^i \binom{s}{i} \binom{2l-r-s}{l-r-i} \\ &= 2 \sum\limits_r t^{-r} \sum\limits_{s} \frac{(rx)^s}{s!} 2^r \sum\limits_{u} \left(\frac{t^2}4\right)^{r+u} \sum\limits_i (-1)^i \binom{s}{i} \binom{r+2u-s}{u-i} \\ &= \sum\limits_{r,s,u} 2^{1-r-2u} t^{r+2u} \frac{(rx)^s}{s!} \sum\limits_i (-1)^i \binom si \binom{r+2u-s}{u-i} \end{aligned} \]
则令 \(n=s,k=r+2u\)，便知 \[ g_k(n) = 2^{1-k} \sum\limits_{2i+r \le k,r\equiv k \pmod 2} r^n (-1)^i \binom ni \binom{k-n}{\frac{k-r}2-i} \]
枚举 \(r\)，则需要计算形如 \[ f_t = \sum\limits_i (-1)^i \binom ni \binom{-s}{t-i} \]
的数列。
考虑其生成函数，显然其为 \[
F(x) = (1+x)^{-s} (1-x)^n
\]
求导 \[ F' = \frac{-sF}{1+x} - \frac{nF}{1-x} \]
即 \[ tf_t = -(n+s)f_{t-1} + (s-n+t-2)f_{t-2} \]
时间复杂度 \(O(k \log_k n)\)。
感觉这题有意思的地方主要在于最前面的 DP 和微分方程部分，以及后面的提取系数部分。
由于这个题很明显是先想题意再想做法的，所以想复刻这种做法的题目还是比较无从下手（好像暴露了啥
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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);
}