Sereja and Subsequences

题目描述

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";
?>