[KMOI R1] 五五五五（Easy）

Luogu

IDLGP9710

Time1000ms

Memory128MB

DifficultyP2

递推O2优化

小宋有一个序列 $a_1,a_2\dots,a_n$，其中对于 $i\in [1,n]$，满足 $a_i\in[0,9]$。对于 $1\le l\le r\le n$，他记 $f(l,r)$ 等于 $\overline{a_la_{(l+1)}\dots a_r}$ 的末尾连续 $5$ 的个数。例如：对于序列 $a=\{1,1,4,5,1,4\}$，$f(2,4)=1,f(1,3)=0$。现在请你求出: $$\Big(\sum\limits_{l=1}^ {n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$ ## Input 第一行一个正整数 $n$，表示序列的长度。第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示序列 $a$。 ## Output 一个正整数 $ans$，表示答案。 [samples] ## Background “迟序之数，非出神怪，有形可检，有数可推。”——祖冲之 ## Note ## 样例 $1$ 解释： $f(1,1)=1$。 $f(1,2)=2$。 $f(2,2)=1$。得到答案 $ans=f(1,1)+f(1,2)+f(2,2)=4$，故输出 $4$。 ## 数据范围 **本题采用 subtask 捆绑测试。** 令 $m=\max\{a_1,a_2,\dots,a_n\}$。 | 子任务编号 | 测试点编号 | $n\le$ | $m\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1$ | $100$ | $3$ | 无 | $3$ | | $2$ | $2\sim 4$ | $2\times 10^5$ | $5$ | $\mathbf{A}$ | $22$ | | $3$ | $5,6$ | $100$ | $5$ | 无 | $10$ | | $4$ | $7\sim 10$ | $2\times 10^5$ | $5$ | $\mathbf{B}$ | $25$ | | $5$ | $11\sim 20$ | $2\times 10^5$ | $9$ | 无 | $40$ | 特殊性质 $\mathbf{A}:$ 序列平均数为 $5$。特殊性质 $\mathbf{B}:$ 序列单调不上升。对于 $100\%$ 的数据：$1\le n\le 2\times 10^5$，$0\le m\le 9$。对于 $\forall i\in [1,n]$，满足 $a_i\in[0,9]$。

Samples

Input #1

2
5 5

Output #1

Input #2

4
1 1 4 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[KMOI R1] 五五五五（Easy）",
    "description": {
      "content": "小宋有一个序列 $a_1,a_2\\dots,a_n$，其中对于 $i\\in [1,n]$，满足 $a_i\\in[0,9]$。 对于 $1\\le l\\le r\\le n$，他记 $f(l,r)$ 等于 $\\overline{a_la_{(l+1)}\\dots a_r}$ 的末尾连续 $5$ 的个数。 例如：对于序列 $a=\\{1,1,4,5,1,4\\}$，$f(2,4)=1,f(1,3)=0$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9710"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小宋有一个序列 $a_1,a_2\\dots,a_n$，其中对于 $i\\in [1,n]$，满足 $a_i\\in[0,9]$。\n\n对于 $1\\le l\\le r\\le n$，他记 $f(l,r)$ 等于 $\\overline{a_la_{(l+1)}\\dots a_r}$ 的末尾连续 $5$ 的个数。\n\n例如：对于序列 $a=\\{1,1,4,5,1,4\\}$，$f(2,4)=1,f(1,3)=0$。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments