[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 D: qwb与神奇的序列 [矩阵]【数学】

2017-06-03 02:12:15 Tabris_ 阅读数：721

博客爬取于2020-06-14 22:40:20
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849656

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1003&pid=3
——————————————————————————————————————————
Problem D: qwb与神奇的序列
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1107 Solved: 163
[Submit][Status][Web Board]
Description
qwb又遇到了一道题目：

有一个序列，初始时只有两个数x和y，之后每次操作时，在原序列的任意两个相邻数之间插入这两个数的和，得到新序列。举例说明：

初始：1 2
操作1次：1 3 2
操作2次：1 4 3 5 2
……
请问在操作n次之后，得到的序列的所有数之和是多少？
Input
多组测试数据，处理到文件结束（测试例数量<=50000）。

输入为一行三个整数x，y，n，相邻两个数之间用单个空格隔开。（0 <= x <= 1e10, 0 <= y <= 1e10, 1 < n <= 1e10）。

Output
对于每个测试例，输出一个整数，占一行，即最终序列中所有数之和。
如果和超过1e8，则输出低8位。（前导0不输出，直接理解成%1e8）
Sample Input
1 2 2
Sample Output
15
——————————————————————————————————————————

先不管x，y的值是什么看看每次x，y对结果贡献多少？
定义（n，m）其中n为x的贡献，m为y的贡献答案就是nx+my

次数	fac	tot
0	(1,0)(0,1)	(1,1)
1	(1,0)(1,1)(0,1)	(2,2)
2	(1,0)(2,1)(1,1)(1,2)(0,1)	(5,5)
3	(1,0)(3,1)(2,1)(3,2)(1,1)(2,3)(1,2)(1,3)(0,1)	(14,14)

然后推出第3列的递推式

$a_i=a_{i-1}*3-1$

由此构造矩阵

$\left[\begin{array}{cc}\ a_i && a_{i+1}\end{array}\right]\times \left[\begin{array}{cc}\ 3 && 0\\ 1&&1\end{array}\right]=\left[\begin{array}{cc}\ a_{i+1} && a_{i+2}\end{array}\right]$

附本题代码
——————————————————————————————————————————

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N = 3000+10;
const int MOD  = 1e8;

const int M = 2;
struct Matrix {
    LL m[M][M];
    void clear0(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=0;
    }
    void clear1(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=(i==j);
    }
    void display(){
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++)
                printf("%lld ",m[i][j]);
            puts("");
        }
        puts("------");
    }
};

Matrix operator * (Matrix &a, Matrix &b){
    Matrix c;c.clear0();

    for(int k=0;k<M;k++)
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;

    return c;
}

Matrix operator ^(Matrix &a,LL b){
    Matrix c;c.clear1();

    while(b){
        if(b&1) c=c*a;
        b>>=1,a=a*a;
    }
    return c;
}
Matrix a,b;
LL x,y,n;
void solve(){
    a.clear0();b.clear0();
    a.m[0][0]=1,a.m[0][1]=-1;

    b.m[0][0]=3,b.m[0][1]=0;
    b.m[1][0]=1,b.m[1][1]=1;

    b=b^(n);
    a=a*b;
    printf("%lld\n",a.m[0][0]*(x+y)%MOD);
}

int main(){
    while(~scanf("%lld%lld%lld",&x,&y,&n))     solve();
    return 0;
}