### shrohit_007's blog

By shrohit_007, history, 2 weeks ago,
question : partition expectation

For an array of Length n, a function is defined as
F(A) = Number of partitions of array A such that each consecutive segment in the partition has a sum in [L,R].

You need to find the expected value of F(A) i.e. (E(F[A])) over all arrays of length n having each element in the range [1,K].

here partition means a division of an array into consecutive segments such that each element belongs to exactly one segment.

Print the expected value for all n in the range [1,N] module 998244353.

you are given four Integers N,K,L,R

1<=N<=1e5
1<=K<=1e6
1<=L<=R<=K

ex 1.

input
2 2 1 2

output
1 748683266

for 1 length
[1] = 1 way
[2] = 1 way
expected value (1+1)/2=1

for 2 length
[1,1]= two way ([1],[1]) , ([1,1])
[1,2]= one way ([1],[2])
[2,1]= one way ([2],[1])
[2,2]= one way ([2],[2])
expected value 5/4


• +1

By shrohit_007, history, 9 months ago,

the question is very simple we just need to calculate total number of numbers which have exactly 4 divisors for ex 6, 8, 10 these are all of the forms p^3 or p*q but here n<=10^11

• 0