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';
}
only for 4 different N values ?
