【每日一题】逆序对
逆序对
https://ac.nowcoder.com/acm/problem/14731
题目
题目描述:
求所有长度为n的01串中满足如下条件的二元组个数：
设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。
答案对1e9+7取模。
输入描述:
输入一个n。
输出描述:
输出答案对1e9+7取模
备注:
n <= 1018
解析
这题目，一看到串长最大可以是18位数就肯定不正常。
所以首先想到的就是把规律（公式）找出来。
因为串超长所以就来找每一位的贡献。
- 当ai为1时，该位则可能有贡献，否则直接舍去
- 找较大位和较小位和ai位之间的关系
- 因为题目中i<j，所以aj是较小位（在ai的后面）
较大位：较大位与二元组没有关系，只会影响到排列组合，大小为
。
较小位：较小位要考虑到形成条件（取0时才可计数）。因为较小位有i-1位数，所以有2i-1种01串，同时串长为i-1。又以为0和1共占总数的一半，所以大小为
)
。
由较大位和较小位可的每一位的值为%5Ctimes2%5E%7Bn-2%7D)
。
所以每一位加起来得到%5Ctimes2%5E%7Bn-2%7D%3Dn%5Ctimes(n-1)%5Ctimes2%5E%7Bn-3%7D)
求出公式以后只要快速幂就行了。。。（算个公式累死本憨憨了）
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int mod = 1e9 + 7;
ll mypow(ll down, ll up);//快速幂
int main() {
js;
ll n; cin >> n;
cout << (n % mod) * ((n - 1) % mod) * mypow(n % mod, n - 3) % mod << endl;
return 0;
}
ll mypow(ll down, ll up) {
ll mul = 1;
while (up) {
if (up & 1) mul = mul * down % mod;
up >>= 1;
down = down * down % mod;
}
return mul;
}
后期补充
邓老师给的超简单理解方法：
- 任选两个位置的方案数是
，其他n个位置随便放的方案数是
，所以总逆序对数就是
。
每日一题 文章被收录于专栏
憨憨的专栏
查看7道真题和解析
公司都抢着要
