HDU 5225 枚舉

題目鏈接：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5225

bc(中文):http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=580&pid=1002

題解：

數組a保存輸入

考慮當前位i，對于1<=j<i，使得x[j]=a[j]，對于第i位，枚舉1<=x[i]<a[i]，并且x[i]!=x[j](1<=j<i)，這樣，對于i<j<=n的部分，任意排列都是滿足條件的

這樣，我們每次計算逆序對可以分為三個部分：

1~i-1的貢獻：

　　計算出所有的a[j](即x[j])>a[k]的個數（1<=j<=i-1，j<k<=n）cnt1（可預處理出來）

第i位的貢獻：

　　計算出所有的x[i]>a[k] (i<k<=n) cnt2

由上面兩部分得：1~i的貢獻：cnt12 =（cnt1+cnt2)*(n-i)!

最后考慮i+1~n的逆序對：

　　在后n-i個位置中，有一半的排列方式中，第j小的數在第k小的數（j>k)的前面。共有(n-i)!種排列方式，所以對于一對數，有（n-i)!/2種排列方式中是逆序對。共有(n-i)*(n-i-1)/2對數，所有這類逆序對共(n-i)*(n-i-1)*(n-i)!/4對。

　　即cnt3=(n-i)*(n-i-1)*(n-i)!/4

綜上：第i位的答案是cnt12+cnt3;

注意:

　　cnt3=(n-i)*(n-i-1)*(n-i)!/4，這里的4要在取模之前處理掉！！！取模之前處理掉！！！取模之前處理掉！！！

　　總共4天提交了11次，CE了2次，wa了6次，ac了3次，最后一次ac告訴我，三天前錯的地方就只有一個！除4沒有提前處理！！！

代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn = 100 + 10;
const int mod = 1e9 + 7;
typedef long long LL;

int arr[maxn], used[maxn];

int n;

LL cnt[maxn];
void pre_for_solve() {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) {
        cnt[i] = cnt[i - 1];
        for (int j = i + 1; j <= n; j++) {
            if (arr[i]>arr[j]) cnt[i]++;
        }
    }
}

LL fac[maxn], fac2[maxn];
void get_fac() {
    memset(fac, 0, sizeof(fac));
    memset(fac2, 0, sizeof(fac2));
    //求1*3*4*...*n
    fac[0] = 1, fac[1] = 1, fac[2] = 1;
    for (int i = 3; i < maxn; i++) {
        fac[i] = fac[i - 1] * i%mod;
    }
    //求1*2*3...*n
    fac2[0] = 1;
    for (int i = 1; i<maxn; i++) {
        fac2[i] = fac2[i - 1] * i%mod;
    }
}

void init() {
    memset(used, 0, sizeof(used));
}

int main() {
    get_fac();
    while (scanf("%d", &n) == 1 && n) {
        init();
        for (int i = 1; i <= n; i++) scanf("%d", arr + i);
        pre_for_solve();
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int x = 1; x<arr[i]; x++) {
                if (!used[x]) {
                    //cnt1
                    LL sum = cnt[i - 1];
                    //cnt2
                    for (int xx = 1; xx <= n; xx++) {
                        if (!used[xx] && x>xx) sum++;
                    }
                    //cnt12
                    sum = sum*fac2[n - i] % mod;
                    //cnt3
                    LL tmp = fac[n - i] * (n - i)*(n - i - 1) / 2 % mod;
                    //cnt12+cnt3
                    sum = (sum + tmp) % mod;
                    ans += sum;
                    ans %= mod;
                }
            }
            used[arr[i]] = 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

?