# PROBLEM LINK:

* Author:* Ildar Gainullin

* Tester:* Alexander Morozov

* Editorialist:* Srikkanth

# DIFFICULTY:

Medium

# PREREQUISITES:

Parseval’s theorem, Fourier transforms, Definite integrals

# PROBLEM:

Evaluate

\int\limits_{0}^{\infty} \frac{e^{2 \pi x}-1}{e^{2 \pi x}+1}(\frac{1}{x}-\frac{x}{N^2+x^2}) dx

# EXPLANATION:

Let the answer be I_N, we can rewrite the integral as

I_N = \int\limits_{0}^{\infty} \tanh(\pi x)(\frac{1}{x}-\frac{x}{N^2+x^2}) dx

We will use Parseval’s theorem for convolution which is :

\int\limits_{0}^{\infty} f(x) g(x) dx = \frac{2}{\pi}\int\limits_{0}^{\infty} F_c(\omega) G_c(\omega) d\omega

where

F_c(\omega) = \int\limits_{0}^{\infty} f(x) sin(\omega x) dx

F_c(\omega) is known as the sine fourier transform of f(x)

Let’s take f(x) = \frac{e^{2 \pi x} - 1}{e^{2 \pi x} + 1} = \tanh(\pi x) and

g(x) = \frac{1}{x} - \frac{x}{N^2 + x^2} and apply Parseval’s theorem.

The fourier transforms for the functions are \mathcal{F}_c\{\tanh(\pi x)\} = \frac{1}{2\sinh(\frac{\omega}{2})} = \frac{1}{e^{\frac{\omega}{2}} - e^{-\frac{\omega}{2}}}

\mathcal{F}_c\{\frac{x}{N^2 + x^2}\} = \frac{\pi}{2} \text{sgn} (\omega) e^{-N | \omega |}

\mathcal{F}_c\{\frac{1}{x}\} = \frac{\pi}{2} \text{sgn}(w)

Substituting we get

I_N = \frac{2}{\pi}\int\limits_{0}^{\infty} \frac{1}{e^{\frac{\omega}{2}} - e^{-\frac{\omega}{2}}} \frac{\pi}{2} \text{sgn} (\omega) (1 - e^{-N | \omega |}) d\omega

\text{sgn}(w) = 1, |\omega| = \omega for the values of \omega in the limits and multiplying the numerator and denominator by e^{-\frac{\omega}{2}} we get,

I_N = \int\limits_{0}^{\infty} \frac{1 - e^{-N \omega}}{1 - e^{-\frac{\omega}{2}}} e^{-\frac{\omega}{2}}d \omega

Using the substitution t = e^{-\frac{\omega}{2}} we get

I_N = 2\int\limits_{0}^{1} \frac{1-t^{2N}}{1-t^2} dt

Clearly I_1 = 2 and

I_N - I_{N-1} = 2 \int_{0}^{1}\frac{t^{2N-2}-t^{2N}}{1-t^2} dt

= 2 \int_{0}^{1}t^{2N-2} dt = \frac{2}{2N-1}

Summing up we get

\sum\limits_{n=2}^{N}I_n - I_{n-1} = \frac{2}{3} + \frac{2}{5} + \ldots \frac{2}{2N-1} = I_N - I_1

\implies I_N = \frac{2}{1} + \frac{2}{3} + \ldots \frac{2}{2N-1}

We can obtain the answer by calculating the fractions I_n for all n by maintaining the numerator and denominator as a_n, b_n for each n from 1 to N.

Specifically if I_n = \frac{a_n}{b_n} then

\frac{a_n}{b_n} = \frac{a_{n-1}}{b_{n-1}} + \frac{1}{2N-1}

\implies a_n = a_{n-1} * (2n-1) + b_{n-1}

b_n = b_{n-1} * (2n-1)

# COMPLEXITY:

**TIME:** \mathcal{O}(N)

**SPACE:** \mathcal{O}(1)

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
const int mod = 998244353;
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int mul(int a, int b) {
return (a * (ll) b) % mod;
}
int pw(int a, int n) {
int ret = 1;
while (n) {
if (n % 2 == 0) {
a = mul(a, a);
n /= 2;
} else {
ret = mul(ret, a);
n--;
}
}
return ret;
}
int inv(int x) {
return pw(x, mod - 2);
}
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= 2 * n; i++) {
int x = mul(inv(i), 1 + (i > n));
add(ans, x);
}
cout << ans << '\n';
}
```