NEU1686 Sort（DP 树状数组）

February 15, 2016

题目链接

题意：题目比较难懂，复制讨论版的内容，为第二个样例的分析：

As we know, there are 27 kinds of permutation of {1,2,3} .

They are

{1,1,1}{1,1,2}{1,1,3}{1,2,1}{1,2.2}{1,2,3}{1,3,1}{1,3,2}{1,3,3}

{2,1,1}{2,1,2}{2,1,3}{2,2,1}{2,2,2}{2,2,3}{2,3,1}{2,3,2}{2,3,3}

{3,1,1}{3,1,2}{3,1,3}{3,2,1}{3,2,2}{3,2,3}{3,3,1}{3,3,2}{3,3,3}

Now, define a new way to sort (given in the test case):2 1 3

which means for each permutation above put all the ‘2’ first,

put all the ‘1’ after all the ‘2’, and then put all the ‘3’ after all the ‘1’.

After that, if this kind permutation is in ascending order.It can be count!

So {1,1,1}{1,1,3}{1,3,1}{1,3,3} {2,2,2}{2,2,3}{2,3,2}{2,3,3}

{3,1,1}{3,1,3}{3,2,2}{3,2,3}{3,3,1}{3,3,2}{3,3,3} THIS 15 kinds can be counted.

思路：做这题前先做这道题（UESTC1217）。这题就是 UESTC1217 的加强版，多了一个 DP：cnt[i][j]（i 个不同的数排 j 个位置所有的方案数）。比如说 1 和 2 两个数排三个位置，可能是 112，121，122，211，212，221 六种情况。考虑第一位的数字，如果这个数字不同于后面所有的数字，那么后面的数字就是 i-1 个数排 j-1 位；否则就是 i 个数排 j-1 位。第一个数有 i 种可能，所以 dp[i][j] = i*(dp[i-1][j-1]+dp[i][j-1])。时间复杂度为 n^2。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod = 1e9+7;
int n;
long long a[2016][2016];
long long dp[2016][2016];
long long cnt[2016][2016];

struct node{
    int pos;
    int num;
}N[2016];

bool cmp(node x, node y){
    return x.num < y.num;
}

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

void add2(int x,int y,int num){
    for(int i = x; i <= n; i += lowbit(i)){
        a[i][y] += num;
        a[i][y] %= mod;
    }
}

long long sum2(int x,int y){
    long long res = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        res += a[i][y];
        res %= mod;
    }
    return res;
}

int main(){
    //freopen("a.txt", "r", stdin);
    cnt[0][0] = 1;
    for(int i = 1; i <= 2016; i++){
        for(int j = i; j <= 2016; j++){
            cnt[i][j] = i*(cnt[i][j-1]%mod + cnt[i-1][j-1]%mod)%mod;
        }
    }
    while(scanf("%d", &n) != EOF){
        memset(dp, 0, sizeof(dp));
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++){
            scanf("%d", &N[i].num);
            N[i].pos = i;
        }
        sort(N+1, N+1+n, cmp);
        long long ans = 0;
        add2(1, 0, 1);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i][j] = sum2(N[i].pos, j-1);
                dp[i][j] %= mod;
                if(dp[i][j] == 0) break;
                add2(N[i].pos+1, j, dp[i][j]);
                ans += dp[i][j]*cnt[j][n]%mod;
                ans %= mod;
            }

        }
        cout << ans << endl;
    }
    return 0;
}