matrix_超时
<center>
提交: 26 解决: 10
[提交][状态][讨论版] </center>
问题 H: matrix
时间限制: 1 Sec 内存限制: 256 MB提交: 26 解决: 10
[提交][状态][讨论版] </center>
题目描述
给定两个长度为n的整数序列l和t，分别作为n×n矩阵F的第一列和第一行，并且保证l 1 = t 1。同时矩阵中的任意其他元素Fij由以下递推给定：
F i,j=a·F i,j-1 + b·F i-1,j
给定系数a,b，要求计算Fn,n模10 9+7的值。
F i,j=a·F i,j-1 + b·F i-1,j
给定系数a,b，要求计算Fn,n模10 9+7的值。
输入
第一行包含三个整数n,a,b。第二行包含n个整数l i。第三行包含n个整数t i。n, a, b, l i , t i ≤ 5000。
输出
共一行包含一个整数，表示Fn,n模10 9+7的值。
样例输入
4 3 5
4 1 7 3
4 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; }
投递比亚迪等公司10个岗位 >