题目链接

题目大意

求一个 $n$ 次多项式 $f(x)=\sum_{i=0}^{n}a_ix^i$,最小化:

$$
\int_{0}^{1}(f(x)-e^x))^2 \mathrm{d} x
$$

其中 $f(x)$ 应可以写为:

$$
f(x)=\sum_{i=0}^{n}a_ix^i=\sum_{i=0}^{n}(\sum_{j=0}^{\infty}p_{i,j}e^j)x^i
$$

其中 $p_{i,j}$ 是有理数,只需要输出 $p_{i,1},p_{i,0}$ 对 $998244353$ 取模的值即可

其中 $1 \le n \le 200$

算法讨论

首先化简:

$$
\begin{aligned}
&\int_{0}^{1}(f(x)-e^x)^2 \mathrm{d} x \\
=&\int_{0}^{1}f^2(x)-2f(x)e^x)+e^{2x}) \mathrm{d} x \\
=&\left(\sum_{i=0}^{n}\sum_{j=0}^{n}a_ia_j \int_{0}^{1}x^{i+j} \mathrm{d} x\right)
-\left( \sum_{i=0}^{n}2a_i\int_{0}^{1}x^ie^x \mathrm{d} x \right)
+\left( \int_{0}^{1}e^{2x} \mathrm{d} x \right) \\
=&\left(\sum_{i=0}^{n}\sum_{j=0}^{n}\frac{a_ia_j}{i+j+1}\right)
-\left( \sum_{i=0}^{n}2a_i\int_{0}^{1}x^ie^x \mathrm{d} x \right)
+\left( \frac{e^2-1}{2} \right) \\
\end{aligned}
$$

对于 $\int x^ne^x \mathrm{d} x$,可以发现它是这个东西:

$$
\int x^ne^x \mathrm{d} x=C+e^x\sum_{i=0}^{n} (-1)^{n-i} \frac{n!}{i!}x^i
$$

设 $\int x^{n}e^{x} \mathrm{d} x = C+e^{x}A(x)$

于是任意一组解,相当于构造多项式 $A(x)$,满足 $A(x)+A’(x)=x^n$

也就是说:

$$
\begin{aligned}
& \left(\sum_{i=0}^{n}a_ix^i\right) + \left(\sum_{i=0}^{n-1}(i+1)a_{i+1}x^i\right)=x^n \\
=& a_nx^n + \sum_{i=0}^{n-1}\left(a_i+(i+1)a_{i+1}\right)x^i=x^n \\
\end{aligned}
$$

也就是说:

$$
\begin{cases}
a_n=1 \\
a_{i}+(i+1)a_{i+1}=0 \\
\end{cases}
$$

也就是说:

$$
a_i=(-1)^{n-i} n^{\underline {n-i}}
$$

实际上就是:

$$
\int A(x)e^x \mathrm{d}x=C+e^{x}B(x)
$$

只需要构造 $B(x)+B’(x)=A(x)$

也就是说:

$$
\int_{0}^{1} x^ne^x \mathrm{d} x=\left(e\sum_{i=0}^{n} (-1)^{n-i} \frac{n!}{i!}\right)+(-1)^{n+1}n!=b_ne+c_n
$$

其中:

$$
\begin{cases}
b_n=1-nb_{n-1} \\
c_n=-nc_{n-1}
\end{cases}
$$

显然 $b_n,c_n$ 都是整数

于是原式化简为:

$$
\begin{aligned}
&\left(\sum_{i=0}^{n}\sum_{j=0}^{n}\frac{a_ia_j}{i+j+1}\right)
-\left( \sum_{i=0}^{n}2a_i\int_{0}^{1}x^ie^x \mathrm{d} x \right)
+\left( \frac{e^2-1}{2} \right) \\
=&\left(\sum_{i=0}^{n}\sum_{j=0}^{n}\frac{a_ia_j}{i+j+1}\right)
-\left( \sum_{i=0}^{n}2a_i (b_ie+c_i)\right)
+\left( \frac{e^2-1}{2} \right) \\
\end{aligned}
$$

那么不妨多元函数求极值一下,可以得到:

$$
\begin{aligned}
\sum_{j=0}^{n}\frac{a_j}{i+j+1}=2(b_ie+c_i)
\end{aligned}
$$

于是 $a_j$ 可以写成 $k_je+r_j$ 的形式,不妨设 $\frac{a_j}{2}=p_{i,1}e+p_{i,0}$,那么有:

$$
\begin{aligned}
\sum_{j=0}^{n}\frac{p_{j,1}e+p_{j,0}}{i+j+1}=b_ie+c_i
\end{aligned}
$$

那么把 $xe+y$ 看成一个二元组 $(x,y)$,然后这个二元组是可以当作一个数字来处理的,于是就可以直接高斯消元了

时间复杂度

$$
O(n^3)
$$

空间复杂度

$$
O(n^3)
$$