1250: Gobonacci
时间限制: 1 Sec 内存限制: 128 MB 提交: 75 解决: 11 [ ][ ][ ]题目描述
Fibonacci sequence is well-known to us ，f(0)=1，f(1)=1, f(n) = f(n-1)+f(n-2), how nice the recursion! In addition, the is exponential growth in series. Obviously, Goagain was not content with the fact that the series didn’t increased as rapidly as he had expected, therefore, he designed such a function
g(0) = a g(1)= b g(2)=c
g(n)=3*g(n-1)+2*g(n-2)+g(n-3) (n>=2)
Besides, the function was named after Goagain series. What made him distracted was that he could hardly calculate the series.
By the way , goagain without any festival fuck named it Gobonacci sequence
输入
Multiple sets of input data, each set including four positive integers a, b, c ,n ( a, b, c <= 100 , 0<= n <2^60)
输出
Please output the value of g(n), considering the value of g(n) is far too large, output g(n) %100000007 is okay.
样例输入
1 1 1 33 2 1 3
样例输出
610
#includeusing namespace std;struct m{long long int a[3][3]; };long long int big = 100000007;m aa = { 0, 1, 0, 0, 0, 1, 1, 2, 3 };m mul(m a, m b){ int i, j, k; m c; for (i = 0; i < 3;i++) for (j = 0; j < 3; j++) { c.a[i][j] = 0; for (k = 0; k < 3; k++) c.a[i][j] +=( (a.a[i][k]%big) * (b.a[k][j]%big))%big; c.a[i][j] %= big; } return c;}m power(m a, long long int n){ if (n == 1)return a; m b = power(a, n / 2); m c = mul(b, b); if (n % 2 == 1)c = mul(a, c); return c;}int main(){ freopen("in.txt", "r", stdin); long long int a, b, c, n; while (cin >> a >> b >> c >> n){ if (n == 0){ cout << a << endl; continue; } if (n == 1){ cout << b << endl; continue; } if (n == 2){ cout << c << endl; continue; } m ans = power(aa, n-2); cout << (ans.a[2][0] * a + ans.a[2][1] * b + ans.a[2][2] * c) % big << endl; }}