[BZOJ 4361] isn（容斥/DP）

Problem

题目地址

Solution

对于一个长度为 \(i\) 的上升子序列，操作方案数有 \((n-i)!\) 种。

令 \(g[i]\) 表示长度为 \(i\) 的上升子序列的集合，\(g[i]\) 仅记录集合元素个数。考虑 \(g[i]\) 这个集合带来的合法操作方案总数。

全集：对于每一个 \(x \in g[i]\)，操作方案数是 \((n-i)!\)，故集合 \(g[i]\) 带来的操作方案总数为 \(g[i]*(n-i)!\)。（包含不合法方案）

不合法方案数：由 \(y \in g[i+1]\)，\(y\) 中任选一个元素删去，得到的 \(y' \in g[i]\) （\(y'\) 一定属于 \(g[i]\)）即为不合法的操作方案（在上一个操作已经是上升子序列）。不合法的方案数为 \(g[i+1]*(n-i-1)*(i+1)\)

综上，\(g[i]\) 这个集合带来的合法操作方案总数为：

\[g[i]*(n-i)! - g[i+1]*(n-i-1)*(i+1)\]

\(g[i]\) 可以用树状数组加DP算出，复杂度 \(O(n^2 \log n)\)。时间复杂度 \(O(n^2 \log n)\)。

Code

Talk is cheap.Show me the code.

#include
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 2007, mod = 1e9+7;
int n;
int a[N],g[N],btmp[N],jc[N];
struct BIT {
    int c[N];
    inline void Add(int x,int y) {
        while(x <= n) {
            c[x] = (c[x] + y) % mod; x += x & -x;
        }
    }
    inline int Ask(int x) {
        int res = 0;
        while(x > 0) {
            res = (res + c[x]) % mod; x -= x & -x;
        }
        return res;
    }
}T[N];
signed main()
{
    n = read();
    for(int i=1;i<=n;++i) a[i] = btmp[i] = read();
    sort(btmp+1, btmp+1+n);
    int ntmp = unique(btmp+1, btmp+1+n) - btmp - 1;
    for(int i=1;i<=n;++i) a[i] = lower_bound(btmp+1, btmp+1+ntmp, a[i]) - btmp;
    for(int i=1;i<=n;++i) {
        for(int j=n;j>=2;--j) {
            int res = T[j-1].Ask(a[i]);
            g[j] = (g[j] + res) % mod;
            T[j].Add(a[i],res);
        }
        ++g[1]; T[1].Add(a[i],1);
    }
    jc[0] = 1;
    for(int i=1;i<=n;++i) jc[i] = (jc[i-1] * i) % mod;
    int ans = 0;
    for(int i=1;i<=n;++i) {
        ans = (ans + g[i]*jc[n-i]%mod - g[i+1]*jc[n-i-1]%mod*(i+1)%mod + mod) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}
/*
4
1 7 5 3

18
*/

Summary

还是减法原理。