No testdata at current.

ps:

不太懂这些公式怎么算，有懂哥可以写一份标答给塔子哥，塔子哥来出数据

题目内容

$KL$ 散度是机器学习，深度学习等领域中关于分布距离度量的重要的方法。

对于两个给定连续分布 $P$ 和 $Q$ ，他们的 $KL$ 散度定义为 $D_{KL(p||q)} = \int p(x) \log^{p(x)} _{q(x)} dx$ 。

对于两个正态分布 $N(\mu_p,\Sigma _p)$ 和 $N(\mu_q,\Sigma _q)$ ，可以通过简单的运算得知他们的 $KL$ 散度为

$D_{KL(p||q)} = \frac{1}{2} [log\frac{\sum_q}{ \sum_p} - k +(\mu_p -\mu_q)^T\Sigma^{-1}_{q}(\mu_p - \mu_q)+tr\{\Sigma^{-1}_q \Sigma_p\}]$

其中 $|·|$ 表示矩阵的行列式， $tr(·)$ 表示矩阵对角线元素求和， $log$ 以自然对数 $e$ 为底。

现在给定其中一个正态分布 $q$ 为 $N(0,I)$ ，另一个分布 $p$ 为 $N(0,\Sigma^{'}_p)$ ， $\Sigma^{'}_p$ 是一个 $k$ 阶对角阵，试判断这两个正态分布的 $KL$ 散度 $D_{KL(p||q)}$ 是否大于给定闻值 $t$ ，若大于则输出 $1$ ，否则输出 $0$ 。

输入描述

第一行表示为测试数据组数 $T$ ，接下来每一组有 $2$ 行，

一组的第一行为 $k$ 和 $t$ ，矩阵 $\Sigma^{'}_p$ 的维度是 $k \times k$ ， $t$ 为给定阈值。其中 $1\le k \le 10^3$ ， $1\le t \le 10^5$ 。

一组的第二行有有 $k$ 个浮点数，为矩阵 $\Sigma^{'}_p$ 的对角元。

输出描述

这两个正态分布的 $KL$ 散度是否大于给定阈值 $t$ ，若大于则输出 $1$ ，否则输出 $0$ 。

样例

输入

2
3 10.5
4.5 3.4 6.5
3 2.2
4.5 3.4 6.5

输出

0
1