愚直に一つずつ計算をしていくと、 が奇数、 が偶数のときに TLE になってしまう可能性があります。

しかし、 が奇数、 が偶数のときは を計算することによってまとめて処理をすることができます。
よって、この問題を十分高速に解くことができました。