정렬되지 않은 쌍 > 문제은행 : 정보올림피아드&알고리즘



1920 : 정렬되지 않은 쌍

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
18 회   
시도횟수
48 회   

문제

어떤 생성기를 통해 생성된 수열에 대해, 

이 수열이 얼마나 정렬되지 아니했는지 아는 것이 유용할 경우가 있다.

생성기는 다음과 같은 공식을 바탕으로 수열을 생성한다.

 


a1 = 1 이고 ak = (m * ak-1 + c ) % (231-1)



여기서 m과 c는 매개변수(직접 입력 가능한 수) 로 직접 주어지고 m과 c의 값에 따라 다양한 수열을 생성할 수 있다.


위에서 a1,a2,a3,...,an이라는 수열이 정해 졌을 때, 

i<j이고 ai>aj인 쌍이 존재할 경우, 이를 ‘정렬되지 않은 쌍’이라고 한다.

 

이러한 정렬되지 않은 쌍의 경우의 수가 몇 가지 존재하는지 알아보는 프로그램을 작성하라.


입력형식

한 줄에 매개변수 m(1≤m≤2,000,000,000)과 c(1≤c<231-1), 그리고 수열의 길이 n(3≤n≤100,000)가 입력된다.


출력형식

생성된 수열에 대한 정렬되지 않은 쌍의 모든 경우를 출력하라.


입력 예

1000 100 6

출력 예

3

merge sort tree, segment tree, Fenwick Tree

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP