松岡 航太郎
for i from 0 to N-1 cᵢ = 0 for i from 0 to N-1 for j from 0 to N-1 if i+j<N cᵢ₊ⱼ += aᵢ⋅bⱼ else cᵢ₊ⱼ₋ₙ -= aᵢ⋅bⱼ (Nの下付きが打てないのでₙになっている)
b[X]−a[X]⋅s[X]=∑k=0N−1[bk−(∑i+j=k,0≤i,j≤N−1ai⋅sj)−(∑i+j=N+k,0≤i,j≤N−1−ai⋅sj)]Xkb[X]-a[X]⋅ s[X]=∑^{N-1}_{k=0} [b_k-(∑_{i+j=k,0≤i,j≤N-1}a_i⋅s_j)-(∑_{i+j=N+k,0≤i,j≤N-1}-a_i⋅s_j)]X^k b[X]−a[X]⋅s[X]=k=0∑N−1[bk−(i+j=k,0≤i,j≤N−1∑ai⋅sj)−(i+j=N+k,0≤i,j≤N−1∑−ai⋅sj)]Xk
b′=bkai′={ak−i if i≤k−aN+k−i otherwise\begin{aligned} b'&=b_k\\ a'_i&=\begin{cases} a_{k-i}\ \mathrm{if}\ i≤k\\ -a_{N+k-i}\ \mathrm{otherwise} \end{cases} \end{aligned} b′ai′=bk={ak−i if i≤k−aN+k−i otherwise
SampleExtractIndex((a[X],b[X]),k) b̄ = bₖ 𝐚̄ = 0 for i from 0 to k āᵢ = aₖ₋ᵢ for i from k+1 to N-1 āᵢ = -aₙ₊ₖ₋ᵢ //下付きにできないのでNが小文字になっている return (𝐚̄,b̄)
page_number: true