#P1225. 2023.04.15-春招-第四题-01串的回文子串
2023.04.15-春招-第四题-01串的回文子串
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
在古老而神秘的岛国里,流传着一个神秘的传说:如果能够解开岛国里的谜题,就可以得到无尽的财富和荣耀。作为一个勇敢的冒险家,塔子哥听说了这个传说,他深深地被吸引,决定前往这个岛国一探究竟。
在岛国中,塔子哥获得了一个秘密任务:他需要解开一个神秘的数字谜题。他来到了一个神秘的洞穴,里面有一些奇怪的符号和数字。他看到了一个特别的 01 串,由于太长了,他无法记住整个 01 串。
于是他记录下了每一段连续的数字中 0
和 1
的数量,即用一个大小为 n 的数组来表示该数字串,其中第一个元素 a1 表示数字串开头有 a1 个 1
,第二个元素 a2 表示紧接着有 a2 个 0
,第三个元素 a3 表示紧接着有 a3 个 1
,以此类推。这样就表示了一个长度为 ∑i=1nai 的数字串。
然而,这还不是全部的挑战。他需要进一步计算该 01 串中非空回文子串的数量(由于答案可能过大,请对 109+7 取模),才能得到该谜题的答案,但是挑战仅凭他一个人无法解决,所以他需要你的帮助,你能帮帮他吗?
回文的定义:字符串正着读和倒着读相同,例如 101101
是回文串。
子串的定义:字符串取一段连续的部分,例如 011
是 1011
的子串。
第一行输入一个正整致 n ,代表数组的大小。
第二行输入 n 个正整数 ai ,代表数组的元素。
1≤n≤1000 , 1≤ai≤109
回文子串的数量,答案对 109+7 取模。
输入
2
2 1
输出
4
输入
4
1 2 2 1
输出
10
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.