题目
题目描述
求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。
答案对1e9+7取模。
输入描述
输入一个n。
输出描述
输出答案对1e9+7取模
示例1
输入
3
输出
6
说明
备注
\(n \leq 10^{18}\)
题解
知识点：组合数学，枚举。
考虑枚举每对位置 \((i,j)\) 对逆序对产生的贡献。显然，对于每一对位置都有 \(2^{n-2}\) 种方案使得这对位置产生贡献，共有 \(\dfrac{n(n-1)}{2}\) 对位置，因此最终答案为 \(\dfrac{n(n-1)}{2} \cdot 2^{n-2}\) 。
时间复杂度 \(O(\log n)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll n;
cin >> n;
if (n == 1) cout << 0 << '\n';
else if (n == 2) cout << 1 << '\n';
else cout << (n % P) * ((n - 1) % P) % P * qpow(2, n - 3) % P << '\n';
//枚举所有可能的(1，0)对，每对有2^(n-2)种方案，共n(n-1)/2对
return 0;
}