0w1

CFR 314 C. Sereja and Subsequences ( DP, BIT )

Problem - 314C - Codeforces

題意:
給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出,對這些子序列分別求,不比該子序列的字典序大的所有子序列的方案數,的總和,對 1e9 + 7 取模。

資料規模:
The first line contains integer n (1 ≤ n ≤ 1e5). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1e6).

解法:
對於一個確定的非遞減子序列,方案數顯然是所有數字相乘。
考慮 dp[ i ][ j ] : 已考慮前 i 個數,以數值 j 結尾時,方案數。
顯然每多走一個數,只會用到一個 j,所以只要 i 由小到大更新,就不必多存那一維。
考慮數值相異,那麼以 j 結尾的數的方案數會是 f:id:h0rnet:20170315182909p:plain
再考慮如果前面有某個值一樣,那麼其實只是 f:id:h0rnet:20170315182948p:plain
可以想成,會重複計算的是那兩個一樣的值合併為尾的情況。

時間 / 空間複雜度:
O( N + MAXA lg MAXA )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;
const int MAXA = ( int ) 1e6;
const int MOD = ( int ) 1e9 + 7;

int N;
int A[ MAXN ];

struct Fenwick_Tree{
  int dat[ MAXA + 1 ];
  void add( int x, int v ){
    for( int i = x; i <= MAXA; i += i & -i ){
      ( dat[ i ] += v ) %= MOD;
    }
  }
  int sum( int x ){
    int res = 0;
    for( int i = x; i; i -= i & -i ){
      ( res += dat[ i ] ) %= MOD;
    }
    return res;
  }
} ftree;

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  for( int i = 0; i < N; ++i ){
    int v = 1LL * ( ftree.sum( A[ i ] ) + 1 ) * A[ i ] % MOD;
    ( v -= ( ftree.sum( A[ i ] ) - ftree.sum( A[ i ] - 1 ) ) ) %= MOD;
    ftree.add( A[ i ], v );
  }
  int ans = ftree.sum( MAXA );
  if( ans < 0 ) ans += MOD;
  cout << ans << endl;
  return 0;
}