题目
链接：https://ac.nowcoder.com/acm/problem/14731
来源：牛客网
求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。
答案对1e9+7取模。
输入描述:
输入一个n。
输出描述:
输出答案对1e9+7取模
示例1
输入
3
输出
6
说明
备注:
n <= 10^18
思路
n数据可以很大，应该考虑推出公式直接求出答案
根据题意，首先假设出一个长度适当的01串，试着求出符合条件的二元组数，可以发现为，每一位是0的前面1的数量求和，或者每一位是1，后面0的数量求和.
这里我们对第i位是0时对答案的贡献进行讨论，
对于长度位n的字符串并且第i位是0的字符串，他前面1的数量一共有（i-1) * 2^(i-1) / 2（每一位是0或1，共有2^(i-1)种可能，每种可能有(i-1)个字符，1的字符占一半）
所以1的数量有（i-1)*2^(i-2)
第i位后面无论是什么，都不会对第i位的0的贡献产生影响，所以要再乘上后缀的 n-i个字符的所有可能 就是 *2^(n - i)
所以第i位0，对答案的贡献是（i-1)2^(n-2) 。
i从2~n求和得到 ans = n(n-1)*2^(n-3)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll fun(ll x,ll y){
ll f = x;x = 0;while(y){
if(y&1)x = (x + f) %mod;y >>=1;f = (f + f)%mod;}return x;
}ll qqow(ll x){
ll f = 2;ll ans = 1;while(x){
if(x&1)ans = fun(ans,f)%mod;x>>=1;f = fun(f,f)%mod;}return ans;
}int main(){
ll n;cin >> n;ll ans;if(n <= 1){
cout << 0;return 0;}if(n == 2){
cout << 1;return 0;}ans=(n%mod)*((n-1)%mod)%mod*qqow(n-3)%mod;//ans = fun(fun(n,n-1),qqow(n-3));cout << ans << endl;return 0;
}