求助 结构体-矩阵里的一个问题

[Meguminexp]

运行时只过了前面的三个点，自己测试小数的时候也没有发现错误，预计是大数出了问题，所以不知道是不是取mod的方式不太对。

[Meguminexp]

include

using namespace std; const int mod = 10e9 + 7; struct Matrix { long long a, b, c, d; }; Matrix Matrix_multi(Matrix A, Matrix B) { Matrix C; C.a = (A.a B.a)%mod + (A.b B.c)%mod; C.b = (A.a B.b)%mod + (A.b B.d)%mod; C.c = (A.c B.a)%mod + (A.d B.c)%mod; C.d = (A.c B.b)%mod + (A.d B.d)%mod; return C; } int main() { Matrix A, I; long long n, a, b, c, d; cin >> n >> a >> b >> c >> d; A.a = a; A.b = b; A.c = c; A.d = d; I.a = 1; I.b = 0; I.c = 0; I.d = 1; while (n) { if (n % 2) I=Matrix_multi(I, A); A=Matrix_multi(A, A); n /= 2; } A = I; cout << A.a % mod << " " << A.b % mod << endl; cout << A.c % mod << " " << A.d % mod << endl; return 0; }

[Liangzheng-ZL]

代码中没有考虑矩阵元素小于0的情况

[paean4h]

矩阵元素小于0会影响哪里吗，试了下取模和四则运算似乎都不影响而且试算了下较小的数得到的结果是对的啊，但是测试集还是有好多未通过 顺带我的代码如下

#include <iostream>
using namespace std;
struct matrix{
    long long ma[2][2];
};
void mapower(const matrix &p1,const matrix &p2,matrix &p3)
{
    long long tmp[2][2];
    tmp[0][0]=(p1.ma[0][0]*p2.ma[0][0]+p1.ma[0][1]*p2.ma[1][0])%1000000007;
    tmp[0][1]=(p1.ma[0][0]*p2.ma[0][1]+p1.ma[0][1]*p2.ma[1][1])%1000000007;
    tmp[1][0]=(p1.ma[1][0]*p2.ma[0][0]+p1.ma[1][1]*p2.ma[1][0])%1000000007;
    tmp[1][1]=(p1.ma[1][0]*p2.ma[0][1]+p1.ma[1][1]*p2.ma[1][1])%1000000007;
    p3.ma[0][0]=tmp[0][0];p3.ma[0][1]=tmp[0][1];p3.ma[1][0]=tmp[1][0];p3.ma[1][1]=tmp[1][1];
}
void power(matrix &p1,int n)
{
    matrix p2;
    p2=p1;
    while(n)
    {
        if(n%2) mapower(p1,p2,p2);
        mapower(p1,p1,p1);
        n /=2;
    }
    p1=p2;
}
int main()
{    
    int n;
    matrix p;
    cin>>n>>p.ma[0][0]>>p.ma[0][1]>>p.ma[1][0]>>p.ma[1][1];

    if(n==0) {p.ma[0][0]=p.ma[1][1]=1;p.ma[0][1]=p.ma[1][0]=0;}
    else power(p,n-1);
    cout<<p.ma[0][0]<<" "<<p.ma[0][1]<<endl<<p.ma[1][0]<<" "<<p.ma[1][1];
    system("pause");
    return 0;
}

[Rosaceae-w]

同问，试算了一下较小的负数，似乎并没有问题？

[louis1117]

同问，负数会影响什么啊

[chenxie95]

这个矩阵中有一个小问题需要说明下，负数取余的规则，存在“不同语言定义不一样”的问题，在本题中使用的取余规则是： -2 % 1000000007 = 1000000005

[piaoliubc]

考虑了负数取模以后，多过了一个，不知道问题在哪儿

include

include

using namespace std;

const long long cs=pow(10.0,9)+7;

long long mod(long long a) { if(a>=0) { long long b=a % cs; return b; } else { long long b=a % cs; b=b+cs; return b; } }

void jzc(long long a[2][2],long long b[2][2])//把我坑惨了，每做一步就改变了相乘矩阵的值，所以有必要新增一个矩阵 { int c[2][2]={0}; c[0][0]=a[0][0]b[0][0]+a[0][1]b[1][0]; c[0][1]=a[0][0]b[0][1]+a[0][1]b[1][1]; c[1][0]=a[1][0]b[0][0]+a[1][1]b[1][0]; c[1][1]=a[1][0]b[0][1]+a[1][1]b[1][1]; a[0][0]=c[0][0]; a[0][1]=c[0][1]; a[1][0]=c[1][0]; a[1][1]=c[1][1];

} int main() { int n=0; cin>>n; long long x[2][2]={0}; cin>>x[0][0]>>x[0][1]>>x[1][0]>>x[1][1]; long long ans[2][2]={1,0,0,1};//最开始是单位矩阵 while(n) { if(n%2) { jzc(ans,x); } jzc(x,x); n/=2; } for(int i=0;i<2;i++) { cout<<mod(ans[i][0])<<' '<<mod(ans[i][1])<<endl; } return 0; }