牛客每日一题 逆序对 组合数学
逆序对
https://ac.nowcoder.com/acm/problem/14731
这题思路非常巧妙
求有多少个逆序对
不妨转换为求每个逆序对的贡献 每个逆序对的贡献即为 这个逆序对在多少个串中出现
所以总逆序对的个数 ：n*(n-1)/2
对于每个逆序对而言，它可以在:2^(n-2)个子串里出现
所以ans=n*(n-1)/2*2^(n-2)
那肯定Py比较好:
n=input(); p = 10**9 + 7 print(n*(n-1)*2**(n-3)%p)
然后T了：
然后C++：
/*** keep hungry and calm CoolGuang!***/
//#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int maxn=2e6+6;
const int mod=1e9+7;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
b/=2;a=(a*a)%mod;
}
return ans;
}
ll qmul(ll a,ll b){
ll ans=0;
while(b){
if(b&1) ans=(ans+a)%mod;
b/=2;a=(a+a)%mod;
}
return ans;
}
int main()
{
read(n);
if(n==2) printf("1\n");
else
printf("%lld\n",qmul(qmul(n,n-1),qpow(2,n-3)));
return 0;
}
/***
w
***/
