Архив задач

2013 [9-10] Путаница

Вася совсем запутался и не может понять, что делает функция g, которую написал Петя. Объясните ему, каким образом она это делает (Единственное, что Вася точно знает так это то, что на вход g Петя подает положительные значения).

struct k{int m[4];};k m(k m1, k m2){return k{

             m1.m[0]*m2.m[0]+m2.m[2]*m1.m[1],

                 m2.m[1]*m1.m[0]+m1.m[1]*

                    m2.m[3], m2.m[0]*

                m1.m[2]+m2.m[2] *m1.m[3],

           m2.m[1]*m1.m[2]+m1.m[3]*m2.m[3]};}     

   int g(int n) {k p={0,1,1,1};k r={1,0,0,1};while(n)

{ if(n&1)r=m(r, p); p=m(p,p);n >>=1;}return r.m[ 2 ]; }