No.2976 高階多点評価
タグ : / 解いたユーザー数 4
作問者 : 👑
p-adic
/ テスター :
ecottea
注意
この問題の実行時間制限は1000[ms]です。
問題文
実数 $x$ に関する関数 $f(x)$ を
$\displaystyle f(x) := \frac{1}{x^2 + 1} $
と定め、次の問題を考えます：
入力に非負整数 $N$ と実数 $X$ が与えられます。
$\displaystyle \frac{(X^2+1)^{\frac{N}{2} + 1}}{N!} \frac{d^N f}{d x^N}(X) $
を求めてください。ただし $\frac{d^N f}{d x^N}(X)$ は $f(x)$ の $X$ における $N$ 階微分係数を表します。
入力の最初に正整数 $T$ が与えられます。$T$ 個の問題に答えてください。
制約
$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力 $N, X$ をそれぞれ $N_t, X_t$ と置きます。
この時、入力は以下の制約を満たします：
- $T$ は $1 \leq T \leq 10^5$ を満たす整数である。
- $T$ 以下の任意の正整数 $t$ に対し、
- $N_t$ は $0 \leq N_t \leq 200$ を満たす整数である。
- $X_t$ は $|X_t| < 1$ を満たしかつ $10^5 X_t$ が整数である実数である。
入力
入力は以下の形式で標準入力から $1 + T$ 行で与えられます：
- $1$ 行目に $T$ が与えられます。
- $T$ 以下の各正整数 $t$ に対し、$1 + t$ 行目に $N_t, X_t$ が半角空白区切りで与えられます。ただし $X_t$ は後で説明する $5$ 桁小数表示で与えられます。
$T$ $N_1$ $X_1$ $\vdots$ $N_T$ $X_T$
実数 $x$ の $5$ 桁小数表示とは、$x$ の小数表示であって小数部分が $5$ 桁であるもののことです。
小数表示について知らない人向けの説明はこちらです。（クリックで開く）
$x$ の $5$ 桁小数表示とは、以下を満たす文字列 $s$ のことです：
- $9$ 以下の非負整数のみからなる長さ $5$ の数列 $(a_1,a_2,a_3,a_4,a_5)$ であって以下の全てを満たすものが存在する：
- $x \geq 0$ ならば、$x = \sum_{i=1}^{5} 10^{-i} a_i$ である。
- $x < 0$ ならば、$x = - \sum_{i=1}^{5} 10^{-i} a_i$ である。
- $x > 0$ ならば、$s = 0.a_1 a_2 a_3 a_4 a_5$ である。
- $x = 0$ ならば、$s = 0.a_1 a_2 a_3 a_4 a_5$ または $s = -0.a_1 a_2 a_3 a_4 a_5$ である。
- $x < 0$ ならば、$s = - 0.a_1 a_2 a_3 a_4 a_5$ である。
ただし $x$ の $5$ 桁小数表示は一意であるとも存在するとも限らないことに注意してください。
出力
$T$ 以下の各正整数 $t$ に対し、$t$ 行目に $t$ 個目の問題に対する答えを出力してください。
最後に改行してください。
なお、この問題は小数誤差許容問題です。厳密な答えの小数点以下 $5$ 桁精度近似値からの絶対誤差または相対誤差が $10^{-3}$ 以下であれば正解となります。
ただしここで実数 $x$ の小数点以下 $5$ 桁精度近似値とは、大雑把には $x$ の小数表示を小数点以下 $5$ 桁までで打ち切って得られる小数を表します。
小数表示を用いないより正確な説明はこちらです。（クリックで開く）
$x$ の小数点以下 $5$ 桁精度近似値とは、
- $x \geq 0$ ならば、$r \leq x$ を満たしかつ $10^5 r$ が整数である実数 $r$ の最大値
- $x < 0$ ならば、$-x$ の小数点以下 $5$ 桁精度近似値の $-1$ 倍
を表します。
また、ジャッジ側の都合で出力は $500$ 桁未満にしてください。
サンプル
サンプル1
入力
3 0 0.00000 1 -0.00000 2 0.10000
出力
1.00000 0.00000 -0.96039
$1$ つ目の問題の答えは
$\displaystyle \frac{(X_1^2+1)^{\frac{N_1}{2} + 1}}{N_1!} \frac{d^{N_1} f}{dx^{N_1}}(X_1) = \frac{(0.00000^2+1)^{\frac{0}{2} + 1}}{0!} \frac{d^0 f}{dx^0}(0.00000) = 1 \times \left. \frac{1}{x^2+1} \right|_{x = 0.00000} = \frac{1}{0.00000^2+1} = 1 $
です。例えば $1.001$ や $0.999$ も正解となります。
$2$ つ目の問題の答えは
$\displaystyle \frac{(X_2^2+1)^{\frac{N_2}{2} + 1}}{N_2!} \frac{d^{N_2} f}{dx^{N_2}}(X_2) = \frac{((-0.00000)^2+1)^{\frac{1}{2} + 1}}{1!} \frac{d^1 f}{dx^1}(-0.00000) = 1^{\frac{3}{2}} \left. \frac{d}{dx} \frac{1}{x^2+1} \right|_{x = -0.00000} = 1 \times \left( \left. - \frac{2x}{(x^2+1)^2} \right|_{x = -0.00000} \right) = - \frac{2 \times (-0.00000)}{((-0.00000)^2+1)^2} = 0 $
です。例えば $0.001$ や $-0.001$ も正解となります。
$3$ つ目の問題の答えは
$\displaystyle \begin{array}{rcl} \displaystyle \frac{(X_3^2+1)^{\frac{N_3}{2} + 1}}{N_3!} \frac{d^{N_3} f}{dx^{N_3}}(X_3) &\displaystyle = &\displaystyle \frac{(0.10000^2+1)^{\frac{2}{2} + 1}}{2!} \frac{d^2 f}{dx^2}(0.10000) = \frac{1.01^2}{2} \left. \frac{d^2}{dx^2} \frac{1}{x^2+1} \right|_{x = 0.10000} = 0.51005 \left. \frac{d}{dx} \left( - \frac{2x}{(x^2+1)^2} \right) \right|_{x = 0.10000} \\ & & \\ &\displaystyle = &\displaystyle 0.51005 \left. \frac{6x^2-2}{(x^2+1)^3} \right|_{x = 0.10000} = 0.51005 \times \frac{6 \times 0.10000^2 - 2}{((0.10000)^2+1)^3} = 0.51005 \times (-1.882944 \cdots) = -0.960396 \cdots \end{array} $
です。例えば $-0.960$ や $-0.961$ も正解となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。