CFR 314 C. Sereja and Subsequences ( DP, BIT )
題意:
給一個 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 結尾的數的方案數會是
再考慮如果前面有某個值一樣,那麼其實只是
可以想成,會重複計算的是那兩個一樣的值合併為尾的情況。
時間 / 空間複雜度:
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; }