I can solve it in $$$O(n\log n)$$$ now.

Let $$$l = 1$$$, it doesn't matter.

We reform $$$f(x)$$$ to $$$f(x)=\sum\limits_{i = 0}^n a_ip(x)^i$$$.

We now only need to calculate $$$\int_0^1 p(x)^i dx$$$. $$$p(x) = 2x(1-x)$$$.

So it will be $$$\int_0^1 x^i(1-x)^i dx = {i!^2 \over (1+2i)!}$$$.

I don't know why but now it can be solved in $$$O(n\log n)$$$. (I get this by wolfram...)

So anyone knows why: $$$\int_0^1 x^i(1-x)^i dx = {i!^2 \over (1+2i)!}$$$?

https://atcoder.jp/contests/agc032/tasks/agc032_f

Here you go.

By polynomial interpolation. It's very brute.

Sorry about that. My mistake. Now I can only solve it in $$$O(n\log^2n)$$$

That's quite easy. We first reform $$$f(x)$$$ to $$$\sum\limits_{i = 0}^n a_i p(x)^i$$$.

It's $$$O(n^2)$$$.

Then we replace $$$p(x)$$$ with $$${2x(l - x) \over l^2}$$$.

It's $$$O(n^2)$$$.

Where's your Bob.

Oh, by FFT. For it's 998244353.

I think Problem F can be solved directly by calculus in $$$O(n\log n)$$$.

Let

(Which means the probability that a random segment cross point x.)

Then

(Which means the probability that a at least k random segment in n cross point x)

We just need to calculate:

We can solve it in $$$O(n\log n)$$$.

I implement it in $$$O(n^2)$$$ though...

UPD: I can't solve it in $$$O(n\log n)$$$ but $$$O(n\log^2 n)$$$. It's about polynomial interpolation so very brute.

UPD2: It can be solved in $$$O(n\log n)$$$ now. See at here.

That's what i can really understand,thank you very much!!