逆序对 来源 Wannafly挑战赛6

逆序对

https://ac.nowcoder.com/acm/contest/37/C

题意:
给一个计算所有长度为n的01序列的贡献和,每个序列的贡献为对数满足
题解:
我们来考虑第位为对答案产生的贡献。那么对于特定的序列,若就对答案产生贡献,那么的序列就会有个,而要使就有,因此第位为对答案产生的贡献为
因此答案为
代码:

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=750008;
const int mod=1e9+7;
const double eps=1e-6;
const double pi=3.14159265358979;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  ll inv2=inv(2);
  ll n;
  cin>>n;
  if(n==0||n==1)cout<<0<<endl;
  else cout<<n%mod*((n-1)%mod)%mod*inv2%mod*qpow(2,n-2)%mod<<endl;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:35
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务