支持一下 Qiuly /tyt
令 $k$ 减一。
设 $F_k$ 为 $k+1$ 层树的 EGF。
立刻写出
$$
F_k'(x) = F_{k-1}(x) \left(\frac{ \mathrm e^x+\mathrm e^{-x} }2\right) = F_{k-1}(x) \cosh x
$$
初值
$$
F_0 = x
$$
这些东西让我联想起了自己对此类复杂的含微分方程的生成函数递推的失败尝试的回忆，让我有些退缩，但是这题真的是这样做（
设二元生成函数 $\mathcal F(x,t) = \sum\limits_{k\ge 0} F_k(x) t^k$，类似地可以写出
$$
\frac{\partial}{\partial x} \mathcal F = 1 + t\mathcal F \cosh x
$$
容易解得
$$
\mathcal F(x) = \mathrm e^{t\sinh x} \int_0^x \mathrm e^{-t\sinh u} \,\mathrm d u
$$
考察其 $[t^k]$，有
$$
F_k(x) = \sum\limits_{j=0}^k \frac{ (\sinh x)^{k-j} }{(k-j)!} \int_0^x \frac{(-\sinh u)^j}{j!} \,\mathrm d u
$$
注意到积分
$$
\int_0^x \mathrm e^{ju} \,\mathrm d u =
\begin{cases}
\frac{\mathrm e^{jx}-1}j, &j\ne 0 \\
x, &j=0
\end{cases}
$$
这告诉我们 $F_k$ 必然是 $\mathrm e^{cx},x\mathrm e^{cx}$ 的线性组合。并且显然有 $-k \le c \le k$。
通过一些没什么用的技巧可以获得 $O(k^2)$ 的解法，但数据范围显然提示我们洞察整式递推。
设 $F_k(x) = G_k(\sinh x)$，主要是为了简化积分形式，那么根据一开始的递推
$$
\begin{aligned}
F_k(x)
&= \int_0^x G_{k-1}(\sinh u) \cosh x \,\mathrm d u \\
&= \int_0^x G_{k-1}(\sinh u) \,\mathrm d(\sinh u) \qquad \left(\frac{\,\mathrm d(\sinh u)}{\,\mathrm d u} = \cosh u\right) \\
&= \int_0^{\sinh x} G_{k-1}(v) \,\mathrm d v \\
G_k(x)
&= \int_0^x G_{k-1}(v) \,\mathrm d v
\end{aligned}
$$
考察 $F_0(x)=x$，那么 $G_0(x)$ 就应该等于反双曲函数 $\sinh^{-1} x$。由于其 ODE 形式不够简洁，不是那么容易推导递推式，因此我们考虑从其导数 $(\sinh^{-1} x)’ = (1+x^2)^{-1/2}$ 入手。
令其为 $A(x)$，那么立刻知
$$
\begin{aligned}
A'(x)(1+x^2) &= – xA(x) \\
na_n &= (1-n) a_{n-2}
\end{aligned}
$$
设 $B(x) = G_k(x)$，则 $b_n = \frac{a_{n-k-1}}{ n^{ \underline{k+1} } }$ 即 $A(x)$ 积分 $k+1$ 次，代入递推式
$$
\begin{aligned}
(n-k-1)a_{n-k-1}
&= (2-n+k) a_{n-k-3} \\
(n-k-1)b_n n^{ \underline{k+1} }
&= (2-n+k) b_{n-2} (n-2)^{ \underline{k+1} } \\
n(n-1)(n-k-1) b_n
&= -(n-k-1)(n-k-2)^2 b_{n-2} \\
(n-k-1)[n(n-1)b_n + (n-k-2)^2 b_{n-2}]
&= 0
\end{aligned}
$$
接下来讨论一下，发现 $n=k+1$ 时 $b_{n-2}=0,b_n=\frac1{(k+1)!}$，则
$$
\begin{aligned}
n(n-1)b_n + (n-k-2)^2 b_{n-2}
&= \frac{[n=k+1]}{(k-1)!} \\
n(n-1)b_n + [(n-2)(n-1)+(1-2k)(n-2)+k^2] b_{n-2}
&= \frac{[n=k+1]}{(k-1)!} \\
k^2 x^2 B + (1-2k)x^3 B’ + x^2(1+x^2)B”
&= \frac{ x^{k+1} }{(k-1)!} \\
k^2 B + (1-2k)x B’ + (1+x^2)B”
&= \frac{ x^{k-1} }{(k-1)!}
\end{aligned}
$$
为了方便计算，我们作换元 $x = \ln x$，那么需要提取的系数就变成了 $x^c,x^c \ln x$。
设 $X = \frac{x-1/x}2$，令 $P(x) = B(X)$，为了导出 $P$ 的 ODE，我们事先作一些计算：
$$
\begin{aligned}
P'(x)
&= \left(\frac{ 1+x^{-2} }2\right) B'(X) \\
P”(x)
&= \left(\frac{ 1+x^{-2} }2\right)^2 B”(X) – x^{-3} B'(x) \\
\Rightarrow B'(x)
&= \left(\frac2{ 1+x^{-2} }\right) P'(x) \\
B”(x)
&= \left(\frac2{ 1+x^{-2} }\right)^2 P”(x) + x^{-3}\left(\frac2{ 1+x^{-2} }\right)^3 P'(x)
\end{aligned}
$$
强行代入再经过一番化简后可得
$$
k^2 (1+x^2) P(x) + ((1+2k)x + (1-2k)x^3) P'(x) + ( x^2+x^4) P”(x) = \frac{X^{k-1}}{(k-1)!} \cdot (1+x^2)
$$
令 $g_n$ 为其 $[x^n \ln x]$，可得
$$
(n+k)^2 g_n + (n-k-2)^2 g_{n-2} = 0
$$
令 $f_n$ 为其 $[x^n]$，可得
$$
(n+k)^2 f_n + (n-k-2)^2 f_{n-2} + 2(n+k)g_n + 2(n-k-2)g_{n-2} = [x^n] \frac{X^{k-1}}{(k-1)!} (1+x^2)
$$
考虑边界值，复习一下前面解出的微分方程可知
$$
\begin{aligned}
f_k &= \frac 1{2^k}\sum_{j=1}^k \frac{(-1)^j}{(k-j)!j!\cdot j} \\
g_k & = \frac 1{2^kk!}
\end{aligned}
$$
如此从大至小递推即可。
代码：
#include <cstdio>
#include <cstring>
using namespace std;
const int K = 1e7 + 2;
const int mod = 998244353;
const int inv2 = 499122177;
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;
}
int k;
long long n;
int fac[K + 5],ifac[K + 5],inv[K + 5];
int vis[K + 5],cnt,prime[K + 5],pw[K + 5];
int f[K + 5],g[K + 5],ans;
int main()
{
scanf("%d%lld",&k,&n),--k;
fac[0] = 1;
for(register int i = 1;i <= k;++i)
fac[i] = (long long)fac[i - 1] * i % mod;
ifac[k] = fpow(fac[k],mod - 2);
for(register int i = k;i;--i)
ifac[i - 1] = (long long)ifac[i] * i % mod;
for(register int i = 1;i <= k;++i)
inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
pw[0] = n == 1 ? 1 : 0,pw[1] = 1;
for(register int i = 2;i <= k;++i)
{
if(!vis[i])
pw[prime[++cnt] = i] = fpow(i,(n - 1) % (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;
}
}
n %= mod;
f[k] = (long long)ifac[k] * fpow(2,mod - 1 - k) % mod;
for(register int i = k - 2;i >= 0;i -= 2)
f[i] = f[i + 2] * (mod - (long long)(i + 2 + k) * (i + 2 + k) % mod) % mod * inv[k - i] % mod * inv[k - i] % mod;
for(register int i = k;i > 0;i -= 2)
ans = (ans + (long long)f[i] * pw[i] % mod * n) % mod;
ans = (ans + (long long)f[0] * pw[0] % mod * n % mod * inv2) % mod;
int t = fpow(2,mod - k);
for(register int i = 0;2 * i <= k - 1;++i)
g[k - 1 - 2 * i] = (long long)(i & 1 ? mod - t : t) * ifac[i] % mod * ifac[k - 1 - i] % mod;
for(register int i = k + 1;i >= 2;i -= 2)
g[i] = (g[i] + g[i - 2]) % mod;
for(register int i = 2;i <= k + 2;++i)
g[i] = (g[i] + (long long)(mod - f[i - 2]) * (mod + 2 * (i - k - 2)) + (long long)(mod - f[i]) * (2 * (i + k))) % mod;
f[k] = 0;
for(register int i = 1;i <= k;++i)
f[k] = (f[k] + (long long)(i & 1 ? mod - inv[i] : inv[i]) * ifac[i] % mod * ifac[k - i]) % mod;
f[k] = (long long)f[k] * fpow(2,mod - 1 - k) % mod;
for(register int i = k - 1;i >= 0;--i)
f[i] = (f[i + 2] * (mod - (long long)(i + 2 + k) * (i + 2 + k) % mod) + g[i + 2]) % mod * inv[k - i] % mod * inv[k - i] % mod;
for(register int i = 1;i <= k;++i)
ans = (ans + (long long)f[i] * pw[i] % mod * i) % mod;
ans = 2 * ans % mod;
printf("%d\n",ans);
}
0 条评论