每日一题：逆序对

题意

题意很简单，求长度为n的01串逆序对数量和。( n <= 1e18 )

solution

任意选两个位置 $i, j$ $(i < j)$，令 $a[i] = 1, a[j] = 0$，这样一定能产生逆序对，这样有 $C_n^2$ 种选法。剩下的位置随便放，有$2^{n-2}$种选法，总方案数即为答案。( 注意 1 需要特判 )

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

ll qp(ll a, ll b) {
  if (b == -1) return 0;
  ll ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}

int main() {
  ll n, res;
  cin >> n;
  res = (((n % mod) * ((n - 1) % mod) / 2 % mod) * qp(2, n - 2) % mod);
  cout << res << '\n';
  return 0;
}