逆序对

[编程题]逆序对

热度指数：22 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

输入描述:

输入一个n。

输出描述:

输出答案对1e9+7取模

示例1

输入

输出

说明

备注:

 n <= 10¹⁸

算法知识视频讲解

fuzhiji

发表于 2020-04-15 15:18:48

方法一：找规律+快速幂假设需要构成长度为n的字符串，任取其中两个元素组成1 0，那么会有种选择方法是不一样的，对于长度为n的字符串，选择一种方法后，还会剩下个字符，每个字符可以是0或1，那么就有种可能，所以可以推出答案式子因为有个取模操作，所以除法要换成乘法，因为这题的公式可以抵消，所以不需要求逆展开全文

wxyww

发表于 2020-04-15 14:02:11

solution 枚举一个为0的位置，然后想办法统计该位置产生的贡献。显然，一个为0的位置产生的贡献就是它前面1的个数。如果位置为0，那么他前面共有种可能的序列，每种序列都有个数字，那么总的数字数量就是。显然的，这些数字中0和1的数量应该是相等的。所以其中1的个数就是。然后考虑后面的位置共有种可能展开全文

Kur1su

发表于 2020-04-15 20:16:12

Solution n >= 1e18, 显然是一道公式题说实话, 这类题我一般是猜公式先说说我怎么猜的已知:n = 1, ans = 0;n = 2, ans = 1;n = 3, ans = 6;由于已知的组数太少, 我们考虑手玩出n = 4的情况n = 4, ans = 24;其次的话, 展开全文

一只橘橘猫

发表于 2020-04-15 13:47:29

题意：解法：时间复杂度： std: #include <bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9 + 7; ll pow_mod(ll a,ll b){ ll 展开全文

shyyhs

发表于 2021-01-11 20:20:32

挺好的一个题目.考虑每组逆序对的贡献,就是,然后有组,然后答案就算它们相乘,注意n==1时输出0.然后注意在做乘法的时候把n%mod.因为n很大. #include <bits/stdc++.h> using namespace std; typedef long long ll; co 展开全文

Devlyp

发表于 2020-04-17 11:02:32

题目描述求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。输入描述: 输入一个n。输出描述: 输出答案对1e9+7取模 #include<bits/stdc++.h> 展开全文

精神病科黄主任

发表于 2020-04-15 12:59:04

考虑从n个位置任取两个，前面位置放1，后面位置放0.所以这是一个组合数n个位置固定了两个位置了，还剩下n-2个位置，每个位置可以放0或者1，是个幂级数所以答案就是进行的除法运算时候，因为模数是个质数，直接用费马小定理即可。当然了，注意特判n=1的情况，因为对于快速幂只能进行非负数，而幂级数的指数部分展开全文