shrohit_007's blog

By shrohit_007, history, 2 weeks ago, In English
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 


ex 1.

2 2 1 2

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 

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By shrohit_007, history, 9 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it