Wannafly挑战赛6 - C 逆序对 (思维)

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位a i和a j（i<j），则a i=1,a j=0。
答案对1e9+7取模。

输入描述:

输入一个n。

输出描述:

输出答案对1e9+7取模

示例1

输入

3

输出

6

说明

备注:

 n <= 1018

每一种串，在最前面加一个1，对答案的贡献就是这个串的0数，加一个0，对答案没有贡献。

所以会有一个推出来的式子

#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define  LL long long
const int maxn = 46000+555;
const LL mod = 1e9+7;

LL qkm(LL base,LL mi)
{
	LL ans=1;
	while(mi){
		if(mi&1) ans=ans*base;
		ans%=mod;
		mi>>=1;
		base=base*base;
		base%=mod;
	}
	return ans;
}

int main()
{

	LL n;
	cin>>n;
	if(n==0||n==1){
		printf("0\n");
	}else if(n==2){
		printf("1\n");
	}else{
		LL a=qkm(1LL*2,n-3);
		n=n%mod;
		printf("%lld\n",a*n%mod*(n-1)%mod);
	}
}