【每日一题】逆序对 题解

Solution

n >= 1e18, 显然是一道公式题
说实话, 这类题我一般是猜公式
先说说我怎么猜的
已知:
n = 1, ans = 0;
n = 2, ans = 1;
n = 3, ans = 6;
由于已知的组数太少, 我们考虑手玩出n = 4的情况

n = 4, ans = 24;
其次的话, 因为是01串, 一共有种摆放情况
我们考虑从的方向猜
可以看出

正经题解:
有n个地方可以放数字, 我们考虑在n个位置中取两个位置i, j(i < j) 令 a[i] = 1, a[j] = 0, 形成全部逆序对,
然后其他位置任意放置, 计算每个逆序对在每个字符串中的贡献
于是得到总的方案是, 证明上面的猜想是正确的
对了, 记得用快速乘!

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 1e9 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
inline ll ksc(ll x, ll y, ll p){
    ll z = (long double)x / p * y;
    ll res = (unsigned long long)x * y - (unsigned long long)z * p;
    return (res + p) % p;
}
ll qpow(ll a, ll b){
  ll res = 1;
  while(b){
    if(b & 1){
      res = ksc(res, a, mod);
    }
    a = ksc(a, a, mod);
    b >>= 1;
  }
  return res;
}
int main(){
  ll n;
  cin >> n;
  if(n == 1) cout << 0 << "\n";
  else if(n == 2) cout << 1 << "\n";
  else 
  cout << ksc(ksc(qpow(2, n - 3), n, mod), n - 1, mod) << "\n";
  return 0;
}