Logs Stacking（第二届中国计量大学ACM程序设计竞赛个人赛）

链接：https://ac.nowcoder.com/acm/contest/3190/I
来源：牛客网

示例1
输入
5
1
3
5
7
2000000000

输出
1
2
5
13
3125

说明
In the third sample, you can accumulate 5 logs within such following ways:
First, you can put all the 5 logs at the ground floor.
Then, you can put 4 logs at the bottom layer, and there are 3 positions for the last log to pile up.
After that, you can also put 3 logs at the bottom layer, while the other 2 logs at the top layer.
Above all, you can get 1 + 3 + 1 = 5 figures in order to accumulate 5 logs.

本题其实就是一个斐波那契数，但是卡时间，所以运用矩阵快速幂快速求出斐波那契数即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
using namespace std
 
const int maxn = 2
const int mod = 10000
 
struct ma
{
    int a[maxn][maxn]
    void init()
    {  
        memset(a, 0, sizeof(a))
        for (int i = 0 i < maxn ++i) a[i][i] = 1
    }
}
 
 
ma mul(ma a, ma b)
{
    ma ans
    for (int i = 0 i < maxn ++i)
    {
        for (int j = 0 j < maxn ++j)
        {
            ans.a[i][j] = 0
            for (int k = 0 k < maxn ++k)
            {
                ans.a[i][j] += a.a[i][k] * b.a[k][j]
                ans.a[i][j] %= mod
            }
        }
    }
    return ans
}
 
ma qpow(ma a, int n)
{
    ma ans
    ans.init()
    while (n)
    {
        if (n & 1) ans = mul(ans, a)
        a = mul(a, a)
        n /= 2
    }
    return ans
}
int main()
{
    long long n,T
    scanf("%lld", &T)
    while (T--)
    {
        ma a
        a.a[0][0] = 1
        a.a[0][1] = 1
        a.a[1][0] = 1
        a.a[1][1] = 0
        scanf("%lld", &n)
        ma ans = qpow(a, n)
        printf("%dn", ans.a[0][1])
    }
    return 0
}