逆序对
找规律做的,下面讲述规律发现的过程:
先写暴力观察规律
#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
3*2=6
4*6=24
5*16=80
6*40=240
7*96=672
8*224=1792
9*512=4608
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
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;
}