Problem Statement

Compute the polynomial kernel matrix for a set of 1D training points and the kernel vector for a test point.

The polynomial kernel of degree d with bias c is:

K(x, z) = (x·z + c)^d

Given n training points in 1D, compute:

1. The n × n kernel matrix K where K[i,j] = (X[i]*X[j] + c)^d
2. The n-dimensional test kernel vector k where k[i] = (X[i]*xt + c)^d

Function signature:

def poly_kernel(X: np.ndarray, c: float, d: int, xt: float) -> tuple:
    # returns (K_matrix, test_vec)
    # K_matrix: n x n, test_vec: length n

Input Format

Line 1: n c d — number of training points, bias constant, polynomial degree
Line 2: n space-separated floats — training data
Line 3: one float — test point xt

Output Format

n lines: the kernel matrix rows (6 decimal places each)
1 line: the test kernel vector (6 decimal places)

Example

Input:

3 1 2
1.0 2.0 3.0
2.5

Output:

4.000000 9.000000 16.000000
9.000000 25.000000 49.000000
16.000000 49.000000 100.000000
12.250000 36.000000 72.250000

Derivation

The kernel trick avoids explicit computation of feature maps. For the polynomial kernel K(x,z) = (x·z + c)^d, the implicit feature space corresponds to all monomials up to degree d. For example, with c=1, d=2 and scalar inputs:

K(x, z) = (xz + 1)^2 = x²z² + 2xz + 1 = φ(x)·φ(z)

where φ(x) = [x², √2 x, 1]. The kernel computes the dot product in this feature space in O(1) instead of O(d).

Notes

• For 1D inputs, x·z is just scalar multiplication.
• The kernel matrix is symmetric positive semi-definite.
• K[i,j] = K[j,i] always holds for polynomial kernels.