BZOJ4361 isn

Description

给出一个长度为 $n$ 的序列 $A(A_1,A_2 \cdot A_n)$。如果序列 $A$ 不是非降的，你必须从中删去一个数这一操作，直到 $A$ 非降为止。求有多少种不同的操作方案，答案模 $10^9+7$ 。

Solution

设 $dp[i][j]$ 表示以 $i$ 这个点结尾，长度恰好为 $j$ 的非降子序列的个数

求法要用树状数组维护（还要离散化）

考虑怎么求出答案 令 $g[i]$ 为有多少个长度为 $i$ 的非降子序列即

$$g[i] = \sum\limits_{j=1}^{n} dp[j][i]$$

那么有：将原序列删除到长度为 $i$ 的子序列的方案数是

$$g[i] \cdot (n-i)!$$

乍看很对，仔细一想其实这不是对的：因为并没有考虑在 (i+1) 的时候已经达到状态就不会再继续进行操作

如果当前不合法那么这个序列只有可能是从 $i+1$ 的状态选择了一个数删掉得到的。所以有

$$ans = \sum\limits_{i = 1} ^ {n} g[i] \cdot (n - i)! - (i + 1) \cdot g[i + 1] \cdot (n - i - 1)!$$

时间复杂度：$O(n^2 \log n)$

Code

/**
 * Author: AcFunction
 * Date:   2019-03-04 19:04:32
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)

using namespace std;

void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}

const int N = 2005; 
const ll mod = (ll)1e9 + 7; 

int n, a[N], f[N][N];

ll fac[N], g[N];  

int lb(int x) { return x & (-x); }

struct BIT {
  int c[N]; 
  void add(int x, int d) {
    for(int i = x; i <= N; i += lb(i))
      c[i] += d, c[i] %= mod; 
  }
  int sum(int x) {
    int ret = 0; 
    for(int i = x; i; i -= lb(i)) 
      ret += c[i], ret %= mod; 
    return ret;  
  }
} b[N]; 

int aa[N]; 
map <int, int> mp; int cnt; 

signed main() {
  INIT(); 
  cin >> n; rep(i, 1, n) cin >> aa[i], a[i] = aa[i]; 
  sort(aa + 1, aa + n + 1); 
  rep(i, 1, n) {
    if(!mp[aa[i]]) mp[aa[i]] = ++cnt; 
  }
  rep(i, 1, n) a[i] = mp[a[i]]; 
  rep(i, 1, n) f[i][1] = 1; 
  rep(j, 2, n) {
    rep(i, 1, n) {
      f[i][j] = b[j - 1].sum(a[i]); 
      b[j - 1].add(a[i], f[i][j - 1]); 
    }
  } fac[0] = fac[1] = 1; 
  ll ans = 0; 
  rep(i, 2, n) fac[i] = fac[i - 1] * i % mod; 
  rep(i, 1, n) 
    rep(j, 1, n) 
      g[i] += f[j][i], g[i] %= mod; 
  rep(i, 1, n) {
    ans += ((g[i] * fac[n - i] % mod) - ((i + 1) * g[i + 1] % mod * fac[n - i - 1]) % mod) % mod;
    ans %= mod;  
  } cout << (ans + mod) % mod << endl; 
  return 0; 
}