In fact there is no need to store (and calculate) full (2x2) matrix. Matrix looks like this:

F(n+1) F(n)
F(n) F(n-1)

We know that F(n-1) = F(n+1) - F(n), so all we need is just 2 numbers.

Here's my (prety cryptic) solution based on optimized matrix multiplication.

class Solution {
public:
int climbStairs(int n) {
// {x,y} is result matrix, {a,b} is pow-2 matrix, t is to store temporary values
int x=1, y=0, a=1, b=1, t;
while (n>0) {
if (n&1) {
// {x,y} * {a,b}
t = b*x;
x = a*x + b*y;
y = t + y*(a-b);
}
// {a,b}^2
t = 2*a-b;
a = a*a + b*b;
b *= t;
n >>= 1;
}
return x;
}
};