冬令营DAY3 T1 Matrix

题目描述 Description

生活中，我们常常用 233 表示情感。实际上，我们也会说 2333，23333，等等。于是问题来了：定义一种矩阵，称为 233 矩阵。矩阵的第一行依次是 23, 233，2333，23333，等。此外，对矩阵的第 i 行、第 j 列的元素有 a[i][j] = a[i-1][j] + a[i][j-1]，若 i, j 均大于 1。
　告诉了你矩阵第一列的第 2~n 个元素，你能否算出矩阵的第 n 行、第 m 列的元素呢？

输入描述 Input Description

输入文件包含多组数据（不超过 3 组），每组数据的格式如下：
第一行，两个整数 n, m。
第二行，n-1 个整数，依次是 a[2][1], a[3][1], …, a[n][1]，表示矩阵第一列的第 2~n 个元素。（而 a[1][1] = 23，a[1][2] = 233，a[1][3] = 2333，以此类推）

输出描述 Output Description

输出若干行，每行一个整数，依次表示每组数据的答案模 10000007 后的结果。

样例输入 Sample Input

2 2
1
3 3
0 0
4 8
23 47 16

样例输出 Sample Output

234
2799
72937

数据范围及提示 Data Size & Hint

50% 的测试数据，1 <= m <= 10^6.
100% 的测试数据，1 <= n <= 11，2 <= m <= 10^9，0 <= a[i][1] <= 10^8.

考试时候第一反应骗50分走人，然后果真就骗五十分走人了，想都没想，现在想起十分后悔。

注意到m范围贼大，普通数组肯定存不下，而n的范围那么小，肯定就能想到矩阵快速幂。

对于第一行f(1,i)=10*f(1,i-1)+3，其中f(1,1)=23，以后的行f(i,j)=f(i-1,j)+f(i,j-1);

先设计一个目标矩阵，我们要得到f(n,m)的值，根据套路，那就把f(1,m),f(2,m)...f(n,m)当成一个目标矩阵吧，这个矩阵由f(1,m-1),f(2,m-1)..f(n,m-1)转移而来，根据转移方程以及矩阵乘法规则，我们能很容易找到转移矩阵，这个矩阵大概是这样：

10	0	0	0	0	3
10	1	0	0	0	3
10	1	1	0	0	3
10	1	1	1	0	3
10	1	1	1	1	3
0	0	0	0	0	1

至于最后一行是什么鬼，我们注意到第一行递推式f(1,i)=10*f(1,i-1)+3中那个3很难搞，于是我们就在目标矩阵中最下面再来一个1，这样乘法就方便多了。

当然，上面那个矩阵是不唯一的，当n不同时，矩阵的样子也不同，但都是有规律的。然后，我们对于每一组数据，构造出一组转移矩阵，然后初始的矩阵也很好搞，然后快速幂一波就好了。下面是代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

typedef long long LL;

#define MOD 10000007

inline int read()

{

    int x=,f=;char c=getchar();

    while(!isdigit(c)){if(c=='-')f=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}

    return x*f;

}

struct matrix

{

    int x,y,a[][];//x为列数,y为行数,a[i][j]表示在矩阵中第i-1行，j-1列的数

    matrix(){x=y=;memset(a,,sizeof(a));}

    matrix operator = (const matrix &s)

    {

        x=s.x;y=s.y;

        memcpy(a,s.a,sizeof(s));

        return *this;

    }

    matrix operator * (const matrix &s)const

    {

        matrix c;c.y=y;c.x=s.x;

        for(int i=;i<c.y;i++)

            for(int j=;j<c.x;j++)

                for(int k=;k<x;k++)

                {

                    LL tmp=(LL)(a[i][k]%MOD)*(LL)(s.a[k][j]%MOD);

                    c.a[i][j]=(c.a[i][j]+tmp%MOD)%MOD;//此处一定要多多小心，防止int*int爆炸

                }

        return c;

    }

};

int n,m,ans,mat[];

matrix mod_pow(matrix C,int n)

{

    matrix ret=C,tmp=C;n--;

    while(n)

    {

        if(n&)ret=ret*tmp;

        tmp=tmp*tmp;

        n>>=;

    }

    return ret;

}

int main()

{

    freopen("matrix.in","r",stdin);

    freopen("matrix.out","w",stdout);

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=;i<n;i++)mat[i]=read()%MOD;

        matrix A;A.x=;A.y=n+;A.a[][]=;//构造初始矩阵

        for(int i=;i<n;i++)A.a[i][]=mat[i];A.a[n][]=;

        matrix B;B.x=n+;B.y=n+;//构造转移矩阵

        for(int i=;i<n;i++)B.a[i][]=,B.a[i][n]=;

        B.a[n][n]=;

        for(int i=;i<n;i++)

            for(int j=;j<=i;j++)B.a[i][j]=;

        matrix final=mod_pow(B,m-)*A;

        printf("%d\n",final.a[n-][]);

    }

    return ;

}

这是我第一次用结构体写矩阵，认为很好使。以后就用这个了。以下是模板，还附带一个可调试的print函数，可输出矩阵：

 struct matrix

 {

     int x,y,a[][];//x为列数,y为行数,a[i][j]表示在矩阵中第i-1行，j-1列的数

     matrix(){x=y=;memset(a,,sizeof(a));}

     matrix operator = (const matrix &s)

     {

         x=s.x;y=s.y;

         memcpy(a,s.a,sizeof(s));

         return *this;

     }

     matrix operator * (const matrix &s)const

     {

         matrix c;c.y=y;c.x=s.x;

         for(int i=;i<c.y;i++)

             for(int j=;j<c.x;j++)

                 for(int k=;k<x;k++)

                 {

                     LL tmp=(LL)(a[i][k]%MOD)*(LL)(s.a[k][j]%MOD);

                     c.a[i][j]=(c.a[i][j]+tmp%MOD)%MOD;

                 }

         return c;

     }

 };

 matrix mod_pow(matrix C,int n)

 {

     matrix ret=C,tmp=C;n--;

     while(n)

     {

         if(n&)ret=ret*tmp;

         tmp=tmp*tmp;

         n>>=;

     }

     return ret;

 }

 void print(matrix A)

 {

     for(int i=;i<A.y;i++)

     {

         for(int j=;j<A.x;j++)printf("%d ",A.a[i][j]);

         printf("\n");

     }

 }

巴特西

冬令营DAY3 T1 Matrix

最新文章

热门文章