Open louis1117 opened 2 years ago
考虑矩阵元素小于0的情况
const int mod = 1e9 + 7; using namespace std;
struct m { int a[4]; };
void mult (int a[4],int b[4]) { int c[4]={0}; c[0]=(((a[0]%mod)(b[0]%mod))%mod+((a[1]%mod)(b[2]%mod))%mod)%mod; c[1]=(((a[0]%mod)(b[1]%mod))%mod+((a[1]%mod)(b[3]%mod))%mod)%mod; c[2]=(((a[2]%mod)(b[0]%mod))%mod+((a[3]%mod)(b[2]%mod))%mod)%mod; c[3]=(((a[2]%mod)(b[1]%mod))%mod+((a[3]%mod)(b[3]%mod))%mod)%mod; for (int i=0;i<4;++i) { b[i]=c[i]; } return ; }
int main()
{
int n;
m m1,m2={1,0,0,1};
cin>>n;
for (int i=0;i<4;++i)
{
cin>>m1.a[i];
}
while(n)
{
if (n % 2)
{
mult (m1.a,m2.a);
}
mult (m1.a,m1.a);
n/=2;
}
for (int i=0;i<4;++i)
{
if (m2.a[i]<0)
m2.a[i]=(mod+m2.a[i]%mod)%mod;
else
m2.a[i]=m2.a[i]%mod;
}
cout<<m2.a[0]<<' '<<m2.a[1]<<endl<<m2.a[2]<<' '<<m2.a[3];
return 0;
}
改成这样了多过了一个了,是mod设置错了吗还是什么,想不明白了
后面的测试题,主要问题在于当元素为负的情况下,取模应该是多少的问题;
if (m2.a[i]<0) m2.a[i]=(m2.a[i]%mod+mod)%mod; else m2.a[i]=m2.a[i]%mod; 所以是这段出问题了吗
include
const int mod = 1e9 + 7; using namespace std;
struct m { int a[4]; };
void mult (int a[4],int b[4]) { int c[4]={0}; c[0]=(((a[0]%mod)(b[0]%mod))%mod+((a[1]%mod)(b[2]%mod))%mod)%mod; c[1]=(((a[0]%mod)(b[1]%mod))%mod+((a[1]%mod)(b[3]%mod))%mod)%mod; c[2]=(((a[2]%mod)(b[0]%mod))%mod+((a[3]%mod)(b[2]%mod))%mod)%mod; c[3]=(((a[2]%mod)(b[1]%mod))%mod+((a[3]%mod)(b[3]%mod))%mod)%mod; for (int i=0;i<4;++i) { b[i]=c[i]; } return ; }
int main() { int n; m m1,m2={1,0,0,1}; cin>>n; for (int i=0;i<4;++i) { cin>>m1.a[i]; } while(n) { if (n % 2) { mult (m1.a,m2.a); } mult (m1.a,m1.a); n/=2; } for (int i=0;i<4;++i) { m1.a[i]=m1.a[i]%mod; } cout<<m2.a[0]<<' '<<m2.a[1]<<endl<<m2.a[2]<<' '<<m2.a[3];
}