【归并排序】【逆序对】序列

【题目描述】
生活中，大多数事物都是有序的，因为顺序的美是最令人陶醉的。所以现在RCDH看了不顺的东西就头痛。所以他想让世界变成有序，所以现在RCDH看了不顺的东西就头痛。所以他想让世界变成有序，可是他只是一个无名小辈，所以只好对数字序列下手。据他所知序列的混乱程度是由“逆序对”的个数决定，公式是Q=2^n,其中Q是指混乱程度，n是指这个序列“逆序对”的个数。逆序对是这样定义的：假设序列中第I个数是ai，若存在Iaj，则就为一个逆序对。你的任务是给定一个序列，计算其混乱程度Q。这个数可能会比较大，你只需输出Qmod1991 的结果。
【输入格式】
第一行，整数n，表示序列中有n个数。
第二行，有n个数。
对于30%的数据
2=
对于100%的数据
2=
数列中的每个数不超过10000000的正整数。
【输出格式】
仅一行，Qmod1991 的值。
【输入样例】
4
1 3 4 2
【输出样例】
4

这个，求逆序对的裸题。

分治法先划分区间分别求解最后合并答案

最后求2^K没有使用快速幂的意义

由于要求Q mod C

C为1991 是一个定值

完全可以找出2^K mod C的循环打一个小小的表……

代码如下

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;


int cnt;
int N;
int A[50005];
int T[50005];
const int ANS[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 57, 114, 228, 456, 912, 1824, 1657, 1323, 655, 1310, 629, 1258, 525, 1050, 109, 218, 436, 872, 1744, 1497, 1003, 15,
 30, 60, 120, 240, 480, 960, 1920, 1849, 1707, 1423, 855, 1710, 1429, 867, 1734, 1477, 963, 1926, 1861,
 1731, 1471, 951, 1902, 1813, 1635, 1279, 567, 1134, 277, 554, 1108, 225, 450, 900, 1800, 1609, 1227, 463, 926, 1852, 1713, 1435, 879, 1758, 1525, 1059, 127, 254, 508, 1016, 41, 82, 164, 328, 656, 1312, 633, 1266, 541, 1082, 173, 346, 692, 1384, 777,
 1554, 1117, 243, 486, 972, 1944, 1897, 1803, 1615, 1239, 487, 974, 1948, 1905, 1819, 1647, 1303, 615, 1230, 469, 938, 1876, 1761, 1531, 1071, 151, 302, 604, 1208, 425, 850, 1700, 1409, 827, 1654, 1317, 643, 1286, 581, 1162, 333, 666, 1332, 673, 1346,
 701, 1402, 813, 1626, 1261, 531, 1062, 133, 266, 532, 1064, 137, 274, 548, 1096, 201, 402, 804, 1608, 1225, 459, 918, 1836, 1681, 1371, 751, 1502, 1013, 35, 70, 140, 280, 560, 1120, 249, 498, 996};

void init_file()
{
	freopen("Sequence.in", "r", stdin);
	freopen("Sequence.out", "w", stdout);
}

void merge_sort(int * A, int x, int y,int *T)
{
	if (y - x > 1)
	{
		int mid = x + (y - x) / 2;
		int p = x;
		int q = mid;
		int i = x;
		merge_sort(A, x, mid, T);
		merge_sort(A, mid, y, T);
		while(p < mid || q < y)
		{
			if (q >= y || (p < mid && A[p] <= A[q])) T[i++] = A[p++];
				else
				{
					T[i++] = A[q++];
					cnt += (mid - p);
				}
		}
		for(int i = x; i < y; i++)
		{
			A[i] = T[i];
		}
	}
}

void read_data()
{
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		scanf("%d", A + i);
}

void work()
{
	merge_sort(A, 0, N, T);
	printf("%d", ANS[cnt % 180]);
}

int main()
{
	init_file();
	read_data();
	work();
	return 0;
}

秒客网

【归并排序】【逆序对】序列

相关文章