Nie jestem pewien czy moje rozwiązanie jest poprawne, ale pomyśl co by było gdybyś podszedł do tego zadania od drugiej strony. Co gdybyś od ilości wszystkich spójnych podciągów odjął ilość spójnych podciągów o średniej mniejszej niż P.
Ilość wszystkich spójnych podciągów obliczymy ze wzoru n*(n+1)/2, natomiast problematyczne jest wyznaczenie podciągów o średniej < P. Mój pomysł jest taki, aby obliczyć to w następujący sposób:
1) od każdej liczby a_i ciągu podanego na wejściu odejmij P, co utworzy nam nowy ciąg, w którym niektóre wartości są ujemne, niektóre dodatnie, a niektóre zerami
2) na podstawie tego ciągu oblicz prefiksy, takie że p[0] = 0, a p[i] (gdzie i > 0) jest równe sumie wszystkich elementów ciągu od a_0 do a_{i-1}
3) teraz znajdź liczbę inwersji w tablicy sum prefiksowych
4) otrzymaną liczbę inwersji odejmij od ilości wszystkich spójnych podciągów i powinieneś otrzymać wynik końcowy
To powinno zadziałać, ale tak jak mówiłem, nie mam co do tego pewności.