题目大意：Tom学会了通过写程序求出一个1-n的排列的逆序对数，，但他的老师给了他一个难题： 给出一个1-n的排列，求所有字典序比它小的1-n的排列的逆序对数之和。 Tom一时不知道该怎么做，所以他来找你帮他解决这个问题。 因为数可能很大，答案对109+7取模。 解题思路：从1到n枚举k，表示当前要计算的排列与读入的排列前k-1项相同，而第k项不同。对于每一个k，再枚举一个t，表示当前要计算的排列的第k项是t，所以t要比读入的排列的第k项小，并且不与前k-1个数中的任意一个数相等。 那么，剩下的n-k个数任意排列，都满足字典序小于读入的排列。所以要计算它们的逆序对数之和。可以分情况计算： 1、逆序对中的两个数都在前k-1个位置，可以对于每一个k都暴力计算。 2、逆序对中的一个数在前k-1个位置，另一个数不在，同样可以对于每一个k都暴力计算。 3、逆序对中的一个数在第k个位置，另一个数在后n-k个位置。也可以暴力计算。 4、逆序对中的两个数都在后n-k个位置。这个值可以DP预处理，也可以推出一个式子直接计算。 可以这样考虑：在后n-k个位置中，有一半的排列方式中，第i小的数在第j小的数(i>j)的前面。共有(n-k)!种排列方式，所以对于一对数，有\frac{(n-k)!}{2}种排列方式中是逆序对。共\frac{(n-k)·(n-k-1)}{2}对数，所以这类逆序对共\frac{(n-k)·(n-k-1)·(n-k)!}{4}对。 时间复杂度：O（{n}^{3}）
#include <cstdio>int main() {long long MOD = 1e9 + 7, DP[200] = {0}, per[200] = {1, 1};for (int i = 2; i < 101; i++) {DP[i] = (per[i – 1] * i * (i – 1) / 2 % MOD + i * DP[i – 1] % MOD) % MOD;per[i] = per[i – 1] * i % MOD;}int N, A[200];while (scanf(“%d”, &N) != EOF) {for (int i = 0; i < N; i++)scanf(“%d”, &A[i]);int vis[200] = {0};long long ans = 0, cnt = 0;for (int i = 0; i < N; i++) {for (int j = 1; j < A[i]; j++)if (!vis[j]) {ans = (((ans + cnt * per[N – i – 1]) % MOD + DP[N – i – 1]) % MOD);cnt++;}vis[A[i]] = 1;}printf(“%lld\n”, ans);}return 0;}
你并不一定会从此拥有更美好的人生，
