kmjp's blog

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

yukicoder : No.1540 級数おもちゃ

yukicoder

ここら辺の数学問、知らない知識がポンポン出てきて大変。
https://yukicoder.me/problems/no/1540

問題

整数列Aが与えられる。
\displaystyle\sum_{i=0}^\infty\binom{2i}i\frac1{16^i}\sum_{j=1}^N\frac{A_j}{2i+j}を求めよ。

なお、この値は有理数a,b,cを用いて a+b\sqrt{3}+c\piの形で表現できるので、a,b,cを答えよ。

解法

元の式を変形していく。詳細はEditorial参照。
\displaystyle \sum_{i=0}^\infty\binom{2i}i\frac1{16^i}\sum_{j=1}^N\frac{A_j}{2i+j} = \sum_{j=1}^NA_j2^j\int_0^{\frac\pi6}\sin^{j-1}\theta d\theta

最後の式について \displaystyle I_n = \int_0^{\frac\pi6}\sin^n}\theta d\thetaとする。
右辺を部分積分していくと、 \displaystyle I_n=\frac{n-1}{n}I_{n-2}-\frac{\sqrt{3}}{n2^n}となる。
I_0, I_1を愚直に計算して求めれば、そこから I_nを求めることができる。

int N;
ll A[101010];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll I[3][101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	I[2][0]=modpow(6);
	I[0][1]=1;
	I[1][1]=mo-modpow(2);
	for(i=2;i<=N+2;i++) {
		I[0][i]=I[0][i-2]*(i-1)%mo*modpow(i)%mo;
		I[1][i]=I[1][i-2]*(i-1)%mo*modpow(i)%mo;
		I[2][i]=I[2][i-2]*(i-1)%mo*modpow(i)%mo;
		(I[1][i]+=mo-modpow(i*modpow(2,i)%mo))%=mo;
	}
	
	ll ret[3]={};
	FOR(i,N) {
		ll p=A[i]*modpow(2,i+1)%mo;
		(ret[0]+=p*I[0][i])%=mo;
		(ret[1]+=p*I[1][i])%=mo;
		(ret[2]+=p*I[2][i])%=mo;
	}
	cout<<ret[0]<<" "<<ret[1]<<" "<<ret[2]<<endl;
	
}

まとめ

複雑な式変形を伴う微積分系の問題、競技プログラミングで余り出てこないせいか苦手意識が強いな。