kmjp's blog

競技プログラミング参加記です

yukicoder : No.2976 高階多点評価

yukicoder

STLの複素数、あまり慣れてない。
https://yukicoder.me/problems/no/2976

問題

$\displaystyle f(x) = \frac{1}{x^2+1}$ とする。
整数N・絶対値1以下の実数Xが与えられるので、
$\displaystyle \frac{(X^2+1)^{\frac{N}{2}+1}}{N!}\frac{d^Nf}{dx^N}(X)$
を求めよ。

解法

f(x)を複素数で因数分解すると
$\displaystyle f(x) = \frac{1}{2i}\left( \frac{1}{x+i}- \frac{1}{x-i}\right)$ となる。
これをN回微分すると求める値は
$\displaystyle (-1)^N\frac{1}{2i}\left((X+i)^{-N-1}-(X-i)^{-N-1} \right)(X^2+1)^{\frac{N}{2}+1}$
なので、複素数の累乗がO(1)と仮定すると式全体の値がO(1)で求められる。

int T,N;
double X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X;
		
		complex<double> X1(X,1),X2(X,-1);
		complex<double> a=pow(-1,N)*(pow(X1,-N-1)-pow(X2,-N-1))/2.0;
		a=a*complex<double>(0,1);
		a=a*pow(X*X+1,N/2.0+1);
		_P("%.12lf\n",a.real());
	}
}

まとめ

あんまり複素数のライブラリ使うことないからなぁ。