【Ah20160703】咏叹 By C

【Ah20160703】咏叹 By C_SUNSHINE

咏叹 By C_SUNSHINE

【试题描述】

Salroey拿到了一个1~n的排列A，她想对这个排列进行冒泡排序：

counter=0

While A不是升序的

counter=counter+1

For i=1 to n-1

If A[i]>A[i+1]

Then Swap(A[i],A[i+1])

End If

End For

End While

现在Salroey想知道，冒泡排序几轮之后，A数组会变得有序呢（即counter变量的值）？

【输入要求】

输入五个整数n,S,B,C,D，n表示数组的长度，用以下方式生成数据：
For i=1 to n
A[i]=i S=(S*B+C) mod D
Swap(A[i],A[(S mod i)+1])
End For

【输出要求】

一行一个正整数，表示冒泡排序进行的轮数。

【输入实例】

4 5 7 9 13

【输出实例】

【其他说明】

对于30%的数据，1 <= n <= 1000
对于50%的数据，1 <= n <= 10^5
对于70%的数据，1 <= n <= 10^6
对于100%的数据，1 <= n <= 3 * 10^7; 0 <= S, B, C < D <= 10^9 + 7

【试题分析】

这道题实在是太6了，这是我们学校的大神去安徽时出的一道数学神题，本来想用归并yy的，但是发现貌似归并只能解决次数，不太好解决轮数。其实正解只有400±B，数据的生成方式是不是非常特别？如果生成数据时没有下面两条语句的话，那么数列就本身是一个符合要求的升序数列。什么才是关键点？swap函数，它交换了两个值，所以我们在求的时候只需要求它现在的下标减去它本身，每次求一个max就可以了。

【代码】

#include<iostream>
using namespace std;
int a[30000001],ans;
int main()
{
	long long n,s,b,c,d;//要设置为long long
    scanf("%lld%lld%lld%lld%lld",&n,&s,&b,&c,&d);
	for(int i=1;i<=n;i++)
	{
	    a[i]=i;
		s=((long long)s*b+c)%d;
		swap(a[i],a[(s%i)+1]);
	}
	for(int i=1;i<=n;i++) ans=max(ans,i-a[i]);
	cout<<ans;
}