描述

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.

Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.

I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.

Input

There are multiple test cases(no more than $20$ cases and no more than $1$ in extreme case), ended by $0$.

For each test cases, the first line contains an integer $n$, meaning the number of shells in this shell necklace, where $1≤n≤10^5$. Following line is a sequence with $n$ non-negative integer $a_1,a_2,…,a_n$, and $a_i≤10^7$ meaning the number of schemes to decorate $i$ continuous shells together with a declaration of love.

Output

For each test case, print one line containing the total number of schemes module $313$(Three hundred and thirteen implies the march 13th, a special and purposeful day).

Hint

For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is $1 + 3 + 3 + 7 = 14$.

思路

• $dp[i]$表示串成长度为$i$的方案数，$dp[0] = 1$。那么转移方程$$dp[i] = \sum_{j = 1} ^ i a[j]dp[i - j]$$
• 这种卷积形式可以使用CDQ分治和FFT求解。
• 假设cdq(l, r)求解$dp[l], dp[l + 1], …, dp[r]$的值。如果已经通过cdq(l, m)求出了左半部分的答案，考虑其对$dp[l], dp[l + 1], …, dp[r]$的贡献。令$g[i]$表示$dp[l], dp[l + 1], …, dp[m]$对$dp[i]$的贡献，那么有$$g[i] = \sum_{j = l}^m dp[j] a[i - j]$$
• 令$x[i] = dp[i + l]$ ，$y[i] = a[i + 1]$，则有
\begin{align*} g[i] &= \sum_{j = l} ^ m dp[j] a[i - j] = \sum_{j = l} ^ m x[j - l] y[i - j - 1] \\ &= \sum_{j = l} ^ {i - 1} x[j - l] y[i - j - 1] \\ &= \sum_{j = 0} ^ {i - l - 1} x[j] y[i - l - 1 - j] = z[i - l - 1] \end{align*}
• $x$序列和$y$序列做一下FFT就好了。
• 不理解的话，可以在草稿纸上单步跑一下……

0%