首页 > 代码库 > matrix_超时

matrix_超时

2024-08-15 13:17:38   217人阅读

问题 H: matrix

时间限制: 1 Sec  内存限制: 256 MB
提交: 26  解决: 10
[提交][状态][讨论版]

题目描述

给定两个长度为n的整数序列l和t，分别作为n×n矩阵F的第一列和第一行，并且保证l1 = t1。同时矩阵中的任意其他元素Fij由以下递推给定：
Fi,j=a·Fi,j-1 + b·Fi-1,j
给定系数a,b，要求计算Fn,n模109+7的值。

输入

第一行包含三个整数n,a,b。第二行包含n个整数li。第三行包含n个整数ti。n, a, b, li , ti ≤ 5000。

输出

共一行包含一个整数，表示Fn,n模109+7的值。

样例输入

4 3 54 1 7 34 7 4 8

样例输出

59716
#include <iostream>#include <cstdio>#include <cmath>using namespace std;int aa[5005][5005];int main(){    int n,a,b;    long int mod=pow(10,9)+7;    scanf("%d %d %d",&n,&a,&b);    for(int i=0;i<n;i++){        scanf("%d",&aa[i][0]);    }    for(int i=0;i<n;i++){        scanf("%d",&aa[0][i]);        if(i>=1){            for(int j=1;j<n;j++){                aa[j][i]=aa[j-1][i]*b+aa[j][i-1]*a;                if(aa[j][i]>mod){                    aa[j][i]%=mod;                }            }        }    }    /*    for(int i=1;i<n;i++){        for(int j=1;j<n;j++){            aa[i][j]=aa[i-1][j]*b+aa[i][j-1]*a;            if(aa[i][j]>mod){                aa[i][j]%=mod;            }        }        for(int j=1;j<n;j++){            aa[j][i]=aa[j-1][i]*b+aa[j][i-1]*a;            if(aa[i][j]>mod){                aa[j][i]%=mod;            }        }    }    */    printf("%d",aa[n-1][n-1]%mod);    return 0;}

 

matrix_超时


联系
我们