题目内容

实现多项式回归算法。

给定数据点 $(x_i, y_i)$ 和多项式阶数 $n$，使用最小二乘法计算回归系数。

多项式形式：$y = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$。

求解方法：构建设计矩阵 $A$（第 $i$ 行为 $[x_i^n, x_i^{n-1}, \ldots, 1]$），求解 $\min_c \|Ac - y\|^2$。

输入描述

第一行输入一个整数 $N$（$3 \le N \le 500$），表示数据点数量。

接下来 $N$ 行，每行两个浮点数 $x$ 和 $y$，表示数据点坐标。

最后一行输入一个整数 $n$（$1 \le n < N$），表示多项式阶数。

输出描述

输出一行，包含 $n+1$ 个浮点数，表示多项式系数，从最高次幂 $a_n$ 到常数项 $a_0$，用空格分隔，保留 $4$ 位小数。

样例 $1$

输入

5
1.0 2.1
2.0 4.9
3.0 7.2
4.0 9.8
5.0 12.1
1

输出

2.49 -0.25

说明

线性拟合 $y = 2.49x - 0.25$，按最小二乘法对 $5$ 个数据点的拟合直线。

样例 $2$

输入

4
0.0 1.0
1.0 2.0
2.0 5.0
3.0 10.0
2

输出

1.00 0.00 1.00

说明

四个点恰好落在 $y = x^2 + 1$ 上，最小二乘系数为 $1$、$0$、$1$。