HDU 2604 매트릭스 신속 멱

제목의 대의.
주어진 길이가 l인 것은 f, m 두 자모의 서열뿐입니다. fff가 나타나지 않느냐고 묻습니다. fmf의 서열 개수는 몇 개입니까?
 
매번 다음 상태는 전번 상태의 뒷글자와 관계가 있다
예를 들어 나는 mm:0, mf:1, fm:2, f:3을 명령한다.
그러면 dp[i][j]는 길이가 i인 서열을 표시하고 마지막에 j상태로 끝나는 총 개수를 나타낸다. 물론 j는 2보다 크다.
dp[i][0] = dp[i-1][0] + dp[i-1][2]
dp[i][1] = dp[i-1][0]
dp[i][2] = dp[i-1][1] + dp[i-1][3]
dp[i][3] = dp[i-1][1]
이 추이 관계에 근거하여 우리는 동적 기획으로 이 문제를 쉽게 풀 수 있다. 그리고 시간이 초과된 것을 발견할 수 있다...
각도를 바꾸어 dp값을 행렬로 본다(dp[i][0], dp[i][1], dp[i][2], dp[i][3]) = {{1,1,0,{0,0,1,1}, {1,0,0,00,{0,0,1,0}*(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3][3], dp[3][3][3]]
 
그리고 연속 곱셈에 최적화를 해요.
while(n){
　　if(n & 1) ~
　　~
　　n>>=1
}

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <iostream>

 4 using namespace std;

 5 int l , M;

 6 

 7 struct Matrix{

 8     int m[4][4];

 9     Matrix operator*(const Matrix &p)const {

10         Matrix tmp;

11         for(int i = 0 ; i < 4 ; i++)

12             for(int j = 0 ; j<4 ; j++){

13                 tmp.m[i][j] = 0;

14                 for(int k = 0 ; k<4 ; k++){

15                     tmp.m[i][j] += m[i][k] * p.m[k][j];

16                     tmp.m[i][j] %= M;

17                 }

18             }

19         return tmp;

20     }

21     void show(){

22         for(int i = 0 ; i<4 ; i++){

23             for(int j = 0 ; j<4 ; j++){

24                 printf("%d " , m[i][j]);

25             }

26             puts("");

27         }

28     }

29 };

30 

31 Matrix pow(Matrix a , int n)

32 {

33     Matrix tmp;

34     memset(tmp.m , 0 , sizeof(tmp.m));

35     //        

36     for(int i = 0 ; i<4 ; i++)

37             tmp.m[i][i] = 1;

38 

39     while(n){

40         if(n & 1) tmp = tmp*a;

41         a = a * a;

42         n >>= 1;

43     }

44     return tmp;

45 }

46 

47 int main()

48 {

49     while(~scanf("%d%d" , &l , &M)){

50         if(l == 0) puts("0");

51         else if(l == 1) printf("%d
" , 2%M);

52         else{

53             Matrix a;

54             a.m[0][0] = 1 , a.m[0][1] = 1 , a.m[0][2] = 0 , a.m[0][3] = 0;

55             a.m[1][0] = 0 , a.m[1][1] = 0 , a.m[1][2] = 1 , a.m[1][3] = 1;

56             a.m[2][0] = 1 , a.m[2][1] = 0 , a.m[2][2] = 0 , a.m[2][3] = 0;

57             a.m[3][0] = 0 , a.m[3][1] = 0 , a.m[3][2] = 1 , a.m[3][3] = 0;

58 

59             Matrix t = pow(a , l-2);

60 

61             int ans = 0;

62             int b[4] = {1 , 1 , 1 , 1};

63             for(int i = 0 ; i<4 ; i++)

64                 for(int j = 0 ; j<4 ; j++){

65                     ans += b[j] * t.m[j][i];

66                 }

67             printf("%d
" , ans % M);

68         }

69     }

70     return 0;

71 }