NOI 2012 난수 생 성기

묘사 하 다.
동 동 은 최근 랜 덤 알고리즘 에 빠 졌 고 랜 덤 생 성 은 랜 덤 알고리즘 의 기초 다.동 동 은 선형 동 여 법 을 사용 하여 무 작위 수열 을 만 들 려 고 한다. 이런 방법 은 네 개의 비 마이너스 매개 변수 m, a, c, X [0] 를 설정 하고 아래 의 공식 에 따라 일련의 무 작위 수 < X [n] >: X [n + 1] = (aX [n] + c) mod m 를 만들어 야 한다. 그 중에서 mod m 는 앞의 수 를 m 로 나 누 는 여 수 를 나타 낸다.이 식 에서 알 수 있 듯 이 이 서열 의 다음 수 는 항상 이전 수가 생 성 된다.
이런 방법 으로 생 성 된 서열 은 무 작위 서열 의 성질 을 가지 기 때문에 이런 방법 은 광범 위 하 게 사용 되 고 있다. 자주 사용 하 는 C + + 와 Pascal 의 무 작위 수 를 생 성 하 는 라 이브 러 리 함 수 를 포함 하여 사용 하 는 것 도 이런 방법 이다. 동 동 은 이렇게 발생 하 는 서열 이 좋 은 임 의 성 을 가지 고 있다 는 것 을 알 지만 마음 이 급 한 그 는 X [n] 가 얼마 인지 빨리 알 고 싶 어 한다.동 에 필요 한 임 의 수 는 0, 1, g - 1 사이 이기 때문에 그 는 X [n] 를 g 으로 나 누 어 원 하 는 수 를 얻 어야 한다. 즉, X [n] mod g 이다. 동 에 게 그 가 원 하 는 수 X [n] mod g 가 얼마 인지 만 알려 주면 된다.
격식.
입력 형식
빈 칸 으로 나 누 는 정수 m, a, c, X0, n 과 g 6 개 를 포함 합 니 다. 그 중에서 a, c, X0 은 비 마이너스 정수, m, n, g 는 정수 입 니 다.
출력 형식
Xn mod g 를 출력 합 니 다.
샘플 1
샘플 입력 1 [복사]
 

11 8 7 1 5 3

샘플 출력 1 [복사]
 

2

제한 하 다.
각 테스트 포인트 1s
제시 하 다.
1: n < = 100, m, a, c, X 0 < = 100 m 는 질 수 2: n < = 1000, m, a, c, X 0 < = 1000 m 는 질 수 3: n < = 10 ^ 4, m, a, c, c, X 0 < = 10 ^ 4m 는 질 수 4: n < = 10 ^ 4, m, a, c, X 0 < = 10 ^ 4 m 는 질 수 5: n < = 10 ^ 5, m, a, a, c, a, c, c, X 0, a, c, X 0 < = 10, a, c, X 0 < = 10 ^ 4 m 와 a - 1 의 이질 6: n < 10 ^ 4 m = 10 ^ 5, m, m, m, a, a, a, c, c, c, X 0 < 10 ^ 4 m 는 질 수 5: n < = 10 ^ 5, 질 7: n < = 10 ^ 5, m, a, c, X0 < = 10 ^ 4 m 와 a - 1 의 상호 질 8: n < = 10 ^ 6, m, a, c, X0 < = 10 ^ 49: n < = 10 ^ 6, m, a, c, X0 < = 10 ^ 9 m 는 질 수 10: n < = 10 ^ 6, m, a, c,X 0 < = 10 ^ 911: n < = 10 ^ 12, m, a, c, X 0 < = 10 ^ 9 m 는 질 수 12: n < = 10 ^ 9 m 은 질 수 12: n < = 10 ^ 12, m, a, c, c, X 0 < = 10 ^ 9 m 는 질 수 13: n < 10 ^ 16, m, a, c, X 0 < = 10 ^ 9 m 와 a - 1 의 호 질 14 n < = 10 ^ 16, m, a, a, c, c, X 0 < = 10 ^ 9 m 와 a - 1 의 호 질 15: n < 10 ^ 16, m, m, a, a, a, m, m, a - 1 과 a - 1 의 10 ^ 16, m, m, a, a, a, c, m, m, m, m, a, a - 1 의 호 질 15: n < 10 = 10 ^ 917: n < = 10 ^ 18, m, a, c, X0 < = 10 ^ 918: n < = 10 ^ 18, m, a, c, X0 < = 10 ^ 18 m 는 질 수 19: n < = 10 ^ 18, m, a, c, X0 < = 10 ^ 18 m 와 a - 1 의 상호 질 20: n < = 10 ^ 18, m, a, c,X0<=10^18
 
기본 사고방식: 매트릭스 + 스피드 幂
이 문 제 는 공식 이 있 는 것 같 지만 인터넷 에 서 는 아무 도 말 하지 않 는 것 같다. 쾌속 멱 의 사상 은 행렬 과 결합 해 야 할 뿐만 아니 라 곱셈 도 필요 하 다.롱 롱 이 직접 곱 하면 폭발 하기 때문에 곱 하기 플러스 로 해 야 합 니 다.
매트릭스 구축

x0 c

a 01 1

출력 은 "% lld"

를 사용 해 야 합 니 다.

 1 #include <iostream>

 2 #include <algorithm>

 3 #include <cstring>

 4 

 5 using namespace std ;

 6 

 7 #define ll long long

 8 

 9 ll m , a , c , n , g , x ;

10 

11 ll multi( ll y , ll cnt ) {

12     if ( ! cnt ) return 0 ;

13     if ( cnt == 1 ) return y % m ;

14     ll rec = multi( y , cnt / 2 ) ;

15     rec = ( rec + rec ) % m ;

16     if ( cnt % 2 ) rec = ( rec + y ) % m ;

17     return rec ;

18 }

19 

20 struct maxtrix {

21     ll a[ 2 ][ 2 ] ;

22     maxtrix(  ) {

23         memset( a , 0 , sizeof( a ) ) ;

24     }

25     void print(  ) {

26         for ( int i = 0 ; i < 2 ; i ++ ) {

27             for ( int j = 0 ; j < 2 ; j ++ ) {

28                 cout << a[ i ][ j ] << " " ;

29             }

30             cout << endl ;

31         }

32     }

33 };

34 

35 maxtrix Multi( maxtrix m1 , maxtrix m2 ) {

36     maxtrix rec ;

37     for ( int i = 0 ; i < 2 ; i ++ ) {

38         for ( int j = 0 ; j < 2 ; j ++ ) {

39             for ( int k = 0 ; k < 2 ; k ++ ) {

40                 rec.a[ i ][ j ] += multi( m1.a[ i ][ k ] , m2.a[ k ][ j ] ) ;

41                 rec.a[ i ][ j ] %= m ;

42             }

43         }

44     }

45     return rec ;

46 }

47 

48 maxtrix Pow( maxtrix x , ll cnt ) {

49     if ( cnt == 1 ) return x ;

50     maxtrix rec = Pow( x , cnt / 2 ) ;

51     rec = Multi( rec , rec ) ;

52     if ( cnt % 2 ) rec = Multi( rec , x ) ;

53     return rec ;

54 }

55 

56 int main(  ) {

57     cin >> m >> a >> c >> x >> n >> g ;

58     maxtrix m1 , m2 ;

59     m2.a[ 0 ][ 0 ] = a , m2.a[ 0 ][ 1 ] = 0 , m2.a[ 1 ][ 0 ] = c , m2.a[ 1 ][ 1 ] = 1 ;

60     m1.a[ 0 ][ 0 ] = x , m1.a[ 0 ][ 1 ] = 1 ;

61     maxtrix ans = Multi( m1 , Pow( m2 , n ) ) ;

62     cout << ans.a[ 0 ][ 0 ] % g << endl ;

63     return 0 ;

64 }