2.18 逆序对

链接：https://ac.nowcoder.com/acm/problem/14731

题意：
求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。
其中\(n <= 1e18\)(好吓人）

考虑推公式，先从n个数中选出两个数i,j。其中a[i] = 1,a[j] = 0，方案数为\(C_n^2\)(就是\(n(n - 1) / 2\)),每个贡献为1（不是2，因为确定了i,j的顺序），其余位置随便选，方案数为2^(n-2),因为分步骤进行，乘一下就好了。

复杂度:O(log(n)) （快速幂必须算）
Code

#include <bits/stdc++.h>
using namespace std;
#define R register
typedef unsigned long long ll;
const ll Mod = 1e9 + 7;
ll ksm(ll x,ll y)
{
	ll ans = 1;
	while(y)
	{
		if(y & 1)ans = (ans * x) % Mod;
		x = (x * x) % Mod;
		y >>= 1; 
	}
	return ans;
}
int main()
{
	ll n;
	scanf("%llu", &n); 
	ll ans = (ksm(2,n - 2) * (((n) % Mod * (((n - 1) + Mod) % Mod)  % Mod) * ksm(2,Mod - 2) % Mod)) % Mod;//n居然也要取模
	printf("%llu", ans);
	return 0;
}

2.18 逆序对

原文：https://www.cnblogs.com/XuKeQAQ/p/14418591.html