#9355. 神秘数字(洛谷 - P2804)

    ID: 9355 Type: Default 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>搜索数学线性数据结构二分递归

神秘数字(洛谷 - P2804)

说明

给定n个数,请你帮助小明求出里面有多少个连续的数的平均数大于给定的某个数M.并将这个方案数输出。注意:这个数可能会很大,所以请输出这个数对92084931取模的结果。

输入格式

两行。第一行为两个数n和M。第二行为n个数。

输出格式

一行一个数,即问题的解对92084931取模的结果

4 3
1 5 4 2
5

提示

【样例解释】

①对于这4个数,问题的解有{5},{4},{5,4},{1,5,4},{5,4,2}共5组。

②对于这4个数,问题的解有{5},{7},{2,7},{7,3},{5,2,7},{5,2,7,3}共6组。

【数据规模】

对于10%的数据,1<n≤10.

对于30%的数据,1<n≤1000.

对于50%的数据,1<n≤30000.

对于100%的数据,1<n≤200000,1<M≤3000,每个数均为正整数且不大于5000.


原题链接

Source

搜索 数学 线性数据结构 二分 递归