HDU4291 A Short problem

求通項和斐波那契數列的方法一樣，矩陣快速冪。

這道題麻煩在套了三層。

但其實取模這種操作肯定會出現循環的，可以先本地暴出循環節，1000000007對應的循環節是222222224，222222224對應的循環節是183120。

最外層的結果是對1000000007取模，它的內層對222222224取模，可以得到相等的答案，那么222222224的內層對183120取模，也能得到相等的答案，這樣就是分別對三個模數做矩陣快速冪，內層得到的結果返回給外層作為指數。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef __int64 LL;
struct Matrix
{
    LL Mt[2][2];
    void init0(){memset(Mt, 0, sizeof(Mt));}
    void init1() {init0(), Mt[0][0] = Mt[1][1] = 1;}
    Matrix(){init0();}
    Matrix(LL num) {init0();Mt[0][0] = Mt[1][1] = num;}
    Matrix(LL a, LL b, LL c, LL d){Mt[0][0] = a, Mt[0][1] = b, Mt[1][0] = c, Mt[1][1] = d;}
    Matrix Mul(const Matrix &b, LL mod)
    {
        int i, j, k;Matrix res;
        for(i = 0; i < 2; ++ i)
            for(j = 0; j < 2; ++ j)
                for(k = 0; k < 2; ++ k)
                    res.Mt[i][j] = (res.Mt[i][j] + Mt[i][k] * b.Mt[k][j]) % mod;
        return res;
    }
    Matrix Rep(LL p, LL mod)
    {
        Matrix b = *this, res(1);
        if(p == 0) return res;
        if(p == 1) return b;
        while(p > 1)
        {
            if(p & 1) res = res.Mul(b, mod);
            b = b.Mul(b, mod);
            p >>= 1;
        }
        return b.Mul(res, mod);
    }
};
LL Cal(LL n, LL mod)
{
    Matrix mm(3, 1, 1, 0), ori(1, 0, 0, 0);
    if(!n) return 0;
    return ori.Mul(mm.Rep(n - 1, mod), mod).Mt[0][0];
}
int main()
{
    LL n;
    while(scanf("%I64d", &n) != EOF)
        printf("%I64d\n", Cal(Cal(Cal(n, 183120), 222222224), 1000000007));
    return 0;
}