Loading [MathJax]/extensions/tex2jax.js

BZOJ4361:isn 题解

解法

这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数,方程为:

\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]

发现可以用树状数组优化,所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\),考虑对答案的贡献。对于一个\(i\),有\(g[i] * (n – i)!\)种方案做变换,但是考虑这\((n – i)!\)中包含了提前变换完成的可能,也就是在我们从合法序列中删去了合法元素的可能,这样肯定是不行的。考虑进行容斥,贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\),表示在这些里选择\(i+1\)个合法元素的方案。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// BZ4361.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_N = 2010, mod = 1e9 + 7;
ll f[MAX_N][MAX_N], g[MAX_N], arr[MAX_N], n, tree[MAX_N][MAX_N], level[MAX_N];
vector<ll> vec;
ll lowbit(ll x) { return x & (-x); }
ll query(ll id, ll x)
{
ll ans = 0;
while (x)
ans = (ans + tree[id][x]) % mod, x -= lowbit(x);
return ans;
}
void add(ll id, ll x, ll d)
{
while (x <= n)
tree[id][x] = (tree[id][x] + d) % mod, x += lowbit(x);
}
int main()
{
scanf("%lld", &n);
for (ll i = 1; i <= n; i++)
scanf("%lld", &arr[i]), vec.push_back(arr[i]);
level[0] = 1;
for (ll i = 1; i < MAX_N; i++)
level[i] = level[i - 1] * i % mod;
sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (ll i = 1; i <= n; i++)
arr[i] = lower_bound(vec.begin(), vec.end(), arr[i]) - vec.begin() + 1;
add(0, 1, 1);
for (ll i = 1; i <= n; i++)
for (ll j = i; j >= 1; j--)
{
f[i][j] = (f[i][j] + query(j - 1, arr[i])) % mod;
add(j, arr[i], f[i][j]);
}
for (ll i = 1; i <= n; i++)
for (ll j = i; j <= n; j++)
g[i] = (g[i] + f[j][i]) % mod;
ll ans = 0;
for (ll i = 1; i <= n; i++)
ans = (ans + g[i] * level[n - i] % mod - g[i + 1] * level[n - i - 1] % mod * (i + 1) % mod + mod) % mod;
printf("%lld", ans);
return 0;
}
// BZ4361.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const ll MAX_N = 2010, mod = 1e9 + 7; ll f[MAX_N][MAX_N], g[MAX_N], arr[MAX_N], n, tree[MAX_N][MAX_N], level[MAX_N]; vector<ll> vec; ll lowbit(ll x) { return x & (-x); } ll query(ll id, ll x) { ll ans = 0; while (x) ans = (ans + tree[id][x]) % mod, x -= lowbit(x); return ans; } void add(ll id, ll x, ll d) { while (x <= n) tree[id][x] = (tree[id][x] + d) % mod, x += lowbit(x); } int main() { scanf("%lld", &n); for (ll i = 1; i <= n; i++) scanf("%lld", &arr[i]), vec.push_back(arr[i]); level[0] = 1; for (ll i = 1; i < MAX_N; i++) level[i] = level[i - 1] * i % mod; sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); for (ll i = 1; i <= n; i++) arr[i] = lower_bound(vec.begin(), vec.end(), arr[i]) - vec.begin() + 1; add(0, 1, 1); for (ll i = 1; i <= n; i++) for (ll j = i; j >= 1; j--) { f[i][j] = (f[i][j] + query(j - 1, arr[i])) % mod; add(j, arr[i], f[i][j]); } for (ll i = 1; i <= n; i++) for (ll j = i; j <= n; j++) g[i] = (g[i] + f[j][i]) % mod; ll ans = 0; for (ll i = 1; i <= n; i++) ans = (ans + g[i] * level[n - i] % mod - g[i + 1] * level[n - i - 1] % mod * (i + 1) % mod + mod) % mod; printf("%lld", ans); return 0; }
// BZ4361.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_N = 2010, mod = 1e9 + 7;
ll f[MAX_N][MAX_N], g[MAX_N], arr[MAX_N], n, tree[MAX_N][MAX_N], level[MAX_N];
vector<ll> vec;

ll lowbit(ll x) { return x & (-x); }

ll query(ll id, ll x)
{
    ll ans = 0;
    while (x)
        ans = (ans + tree[id][x]) % mod, x -= lowbit(x);
    return ans;
}

void add(ll id, ll x, ll d)
{
    while (x <= n)
        tree[id][x] = (tree[id][x] + d) % mod, x += lowbit(x);
}

int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), vec.push_back(arr[i]);
    level[0] = 1;
    for (ll i = 1; i < MAX_N; i++)
        level[i] = level[i - 1] * i % mod;

    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (ll i = 1; i <= n; i++)
        arr[i] = lower_bound(vec.begin(), vec.end(), arr[i]) - vec.begin() + 1;

    add(0, 1, 1);
    for (ll i = 1; i <= n; i++)
        for (ll j = i; j >= 1; j--)
        {
            f[i][j] = (f[i][j] + query(j - 1, arr[i])) % mod;
            add(j, arr[i], f[i][j]);
        }
    for (ll i = 1; i <= n; i++)
        for (ll j = i; j <= n; j++)
            g[i] = (g[i] + f[j][i]) % mod;
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
        ans = (ans + g[i] * level[n - i] % mod - g[i + 1] * level[n - i - 1] % mod * (i + 1) % mod + mod) % mod;
    printf("%lld", ans);
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *