题目大意是给定一串1到n的排列(设为数组a)，求其中满足a[x]
直接求这样的排列个数并不好求，我们可以转化为求a[x]
用left数组记录i位置前比a[i]小的元素个数，left数组可由树状数组预处理得到，那么我们可以得到求排列个数的公式（具体见码）
?
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const LL maxn = 100000 + 5; LL C[2 * maxn], lef[maxn], n; //lef数组表示i之前比a[i]小的数的个数 LL lowbit(LL x) { return x&(-x); } void add(LL x, LL d){ while(x <= n) { C[x] += d; x += lowbit(x); } } LL sum(LL x) { LL ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } int main() { LL t, kase = 0; scanf("%I64d", &t); while(t--) { memset(C, 0, sizeof(C)); scanf("%I64d", &n); LL ans = 0; for(LL i = 1; i <= n; i++) { LL tmp; scanf("%I64d", &tmp); lef[i] = sum(tmp); add(tmp, 1); // prLLf("%I64d\n", lef[i]); ans = ans + (n + lef[i] + 1 - tmp - i) * (n + lef[i] - tmp - i) / 2 - (n + lef[i] + 1 - tmp - i) * lef[i]; } printf("Case #%I64d: %I64d\n", ++kase, ans % 100000007); } return 0; }