题目描述
Sereja has a sequence that consists of $n$ positive integers, $a_1, a_2, \ldots, a_n$.
First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence $a$. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.
A sequence of positive integers $x=x_1, x_2, \ldots, x_r$ doesn’t exceed a sequence of positive integers $y=y_1, y_2, \ldots, y_r$, if the following inequation holds: $x_1 \le y_1, x_2 \le y_2, \ldots, x_r \le y_r$.
Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo $1000000007$ ($10^9+7$).
题意概述
定义一个序列$a_1, a_2, \ldots, a_k$的数量等于长度为$k$且第$i$个元素不大于$a_i$的序列的个数。给定一个长度为$n$的序列,求其所有不下降子序列的数量之和。
数据范围:$1 \le n \le 10^5, \; 1 \le a_i \le 10^6$。
算法分析
显然,对于一个序列$a_1, a_2, \ldots, a_k$,它的数量为$a_1a_2 \cdots a_k$。令$f_i$表示以$i$结尾的不下降子序列的数量之和。设当前枚举到第$i$个数,转移方程如下
$$f_{a_i}=(1+f_1+f_2+ \cdots +f_{a_i})a_i$$
可以用树状数组来维护前缀和。最后得到的$f_1+f_2+ \cdots +f_{10^6}$就是答案。
代码
<?php const MAX_NUM = 1000000; const MOD = 1000000007; $tree = array(); for ($i = 0; $i <= MAX_NUM; ++ $i) array_push($tree, 0); function add($pos, $val) { global $tree; for (; $pos <= MAX_NUM; $pos += $pos & -$pos) { $tree[$pos] += $val; $tree[$pos] -= (int) ($tree[$pos] / MOD) * MOD; } } function get($pos) { global $tree; $ret = 0; for (; $pos; $pos -= $pos & -$pos) { $ret += $tree[$pos]; $ret -= (int) ($ret / MOD) * MOD; } return $ret; } $n = fgets(STDIN); $a = explode(' ', trim(fgets(STDIN))); for ($i = 0; $i < $n; ++ $i) { $sum = get($a[$i]); add($a[$i], $sum * $a[$i] + $a[$i] - $sum + get($a[$i] - 1)); } $ans = get(MAX_NUM); $ans -= (int) ($ans / MOD) * MOD; echo $ans . "\n"; ?>