蒟蒻写矩阵快速幂的时候出现莫名其妙的TLE,仔细检查都没有问题,从题解里面扒了同样使用cin和cout的代码丢洛谷编译器里(下载的第一个测试数据)
(TLE是我的,AC的是题解)
(注意看右下角运行时间)
(答案都是一样的!)
TLE代码
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int n;
long long k;
struct matrix {
long long data[100][100];
friend istream& operator>>(istream& input, matrix &t);
friend ostream& operator<<(ostream& output, matrix &t);
friend matrix operator*(matrix &a, matrix &b);
inline void unit() {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++)
this->data[i][j] = i==j;
}
}
};
istream& operator>>(istream& input, matrix &t) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++)
input >> t.data[i][j];
}
}
ostream& operator<<(ostream& output, matrix &t) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++)
output << t.data[i][j] << ' ';
output << '\n';
}
}
matrix operator*(matrix &a, matrix &b) {
matrix m;
int c;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
c = 0;
for(int r=0; r<n; r++) {
c += (a.data[i][r] * b.data[r][j]) % MOD;
c %= MOD;
}
m.data[i][j] = c;
}
}
return m;
}
matrix a, c;
int main() {
ios::sync_with_stdio(false);
cin >> n >> k >> a;
c.unit();
while(k) {
if(k & 1) {
c = c*a;
k--;
}
else {
a = a*a;
k = k>>1;
}
}
cout << c;
return 0;
}
(不要在意码风)