Chlience

【题解】BZOJ 4361 isn
Problem给定一个长度为 $n$ 的序列,当前序列不是一个非降序列时,可以删掉一个数,问有多少种删除方案Tho...
扫描右侧二维码阅读全文
08
2019/01

【题解】BZOJ 4361 isn

Problem

给定一个长度为 $n$ 的序列,当前序列不是一个非降序列时,可以删掉一个数,问有多少种删除方案

Thought

既然是要删掉成为一个非降序列,那么考虑直接算有多少种结束状态,对于每个结束状态,可以按任意顺序删掉应该删除的点

设 $f[i][j]$ 表示前 $i$ 个点形成了一个长度为 $j$ 的最后一个元素必定为 $a[i]$ 的非降序列的方案数

这个转移很显然,对于每个 $f[i][j]=\sum_{k=1}^{i-1}[a[k]\leq a[i]]*f[k][j-1]$
可以用树状数组维护

同时,我们发现,某些状态是根本达不到的,因为在某些删除顺序下,删除序列未完成就已经变为了一个非降序列
如何将其提取出来呢?

设 $g'[x]$ 为删除 $x$ 个点的方案,未排除非法情况
设 $g[x]$ 为删除 $x$ 个点的方案,排除非法情况

首先考虑删除的最少的方案,假设删除了 $least$ 个点,显然对于这个方案必然不会出现非法情况
接下来计算比上一次多删一个点,即 $least+1$ 个点的方案,当且仅当将序列删为上次的序列时,无法继续删除,所以说需要减去上次序列的贡献乘上 $n-least$,即

$$ g[least+1]=g'[least+1]-g[least]*(n-least) $$

如果计算删除 $least+2$ 个点的方案呢?
那么也就是

$$ g[least+2]=g'[least+2]-g[least+1]*(n-least-1)-g[least]*(n-least)*(n-least-1) $$

发现若将 $g[least+1]$ 代入可得:

$$ g[least+2]=g'[least+2]-g'[least+1]*(n-least-1) $$

发现这个东西对所有位置都成立,所以说 $g[x]=g'[x]-g'[x-1]*(n-x-1)$

当然,你也可以将 $g'$ 看做是瞎删的方案,上次不管是非法的或者是合法的,在当前这次都是重复算的,所以说直接减去即可

于是乎转化成留下 $x$ 个点的方案数就是 $g[x]=g'[x]-g'[x+1]*(x+1)$

答案就是 $\sum_{i=1}^{n}g[x]$

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int mod = 1000000007;
const int N = 2010;
int f[N][N];
int g[N] , t[N] , jc[N];
int dif;
int a[N] , A[N];
int n;
int lowbit(int x) {return x & (-x);}
void add(int pos , int x) {
    if(!pos) return;
    for(; pos <= dif ; pos += lowbit(pos))
        t[pos] = (t[pos] + x) % mod;
} 
int query(int pos) {
    int ans = 0;
    for(; pos ; pos -= lowbit(pos))
        ans = (ans + t[pos]) % mod;
    return ans;
}
int main() {
    n = read();
    for(int i = 1 ; i <= n ; ++ i) A[i] = a[i] = read();
    sort(A + 1 , A + n + 1);
    dif = unique(A + 1 , A + n + 1) - A - 1;
    for(int i = 1 ; i <= n ; ++ i) a[i] = lower_bound(A + 1 , A + dif + 1 , a[i]) - A;
    jc[1] = 1;
    for(int i = 2 ; i <= n ; ++ i) jc[i] = 1ll * jc[i - 1] * i % mod;
    add(1 , 1);
    for(int j = 1 ; j <= n ; ++ j) {
        add(a[j - 1] , f[j - 1][j - 1]);
        for(int i = j ; i <= n ; ++ i) {
            f[i][j] = query(a[i]);
            add(a[i] , f[i][j - 1]);
            g[j] = (g[j] + 1ll * f[i][j] * jc[n - j] % mod) % mod;
        }
        memset(t , 0 , sizeof(t));
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; ++ i)
        ans = (ans + ((g[i] - 1ll * g[i + 1] * (i + 1) % mod) + mod) % mod) % mod;
    printf("%d\n" , ans);
    return 0;
}
Last modification:January 8th, 2019 at 07:00 pm

Leave a Comment