逆序对

找规律做的,下面讲述规律发现的过程:

先写暴力观察规律

#include<bits/stdc++.h>
using namespace std;
#define int long long

// a存储按位拆分结果
int a[64];
// ai表示拆分出的二进制长度
int ai;

// 按位拆分函数
void cf(int x) {
	ai = 0;
	while (x) {
		a[ai++] = x & 1ll;
		x /= 2;
	}
}

signed main() {
    // 暴力计算二进制位1-20的情况
	for (int n = 1; n <= 20; n++) {
        // 枚举的所有数一定小于2^n
		int mx = 1ll << n;
		int ans = 0;// 计次
		for (int i = 0; i < mx; ++i) {
			cf(i);// 先拆分
			for (int j = ai - 1; j >= 0; --j) {// 当成字符串看
				if (a[j]) {// 前面得是1才行
					for (int k = j - 1; k >= 0; --k) {
						if (a[k] == 0) { // 后面有0就算一个
							++ans;
						}
					}
				}
			}
		}
		cout << n << ' ' << ans << '\n';
	}
	return 0;
}

运算结果:

1 0
2 1
3 6
4 24
5 80
6 240
7 672
8 1792
9 4608
10 11520
11 28160
12 67584
13 159744
14 372736
15 860160
16 1966080
17 4456448
18 10027008
19 22413312
20 49807360

alt

3*2=6
4*6=24
5*16=80
6*40=240
7*96=672
8*224=1792
9*512=4608

alt

6=6/1=6*2/2
16=24/1.5=24*2/3
40=80/2=80*2/4
96=240/2.5=240*2/5

alt

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e9+5;
const int p = 1e9+7;

int qpow(int a, int b) {
	int ans = 1;
	for (; b; b >>= 1) {
		if (b & 1) ans = (ans * a) % p;
		a = (a*a) % p;
	}
	return ans;
}

int sv(int n) {
	if (n < 2) {
		return 0;
	}
	if (n == 2) {
		return 1;
	} else if (n == 3) {
		return 6;
	}

	return (n % p) * (((n - 1) % p) * qpow(2, n - 3) % p) % p;
}

signed main() {
	int n;
	cin >> n;
	cout << sv(n);
	return 0;
}