結果
| 問題 |
No.793 うし数列 2
|
| コンテスト | |
| ユーザー |
 potoooooooo
|
| 提出日時 | 2019-02-23 13:42:37 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 8,628 bytes |
| コンパイル時間 | 1,874 ms |
| コンパイル使用メモリ | 179,792 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-29 17:58:05 |
| 合計ジャッジ時間 | 2,681 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007;
template<class Numeric> class Matrix {
protected:
vector< vector<Numeric> > _mat;
int _col, _row;
const bool usingModulo = true;
const Numeric modulo = 1000000007; // using modulo
void resize(int col, int row) {
_col = col; _row = row;
_mat.assign(col, vector<Numeric>(row, 0));
}
public:
Matrix(int col, int row) : _col(col), _row(row) {
_mat.assign(col, vector<Numeric>(row, 0));
}
Matrix(int col, int row, int num) : _col(col), _row(row) {
_mat.assign(col, vector<Numeric>(row, num));
}
int col() const { return _col; }
int row() const { return _row; }
vector<vector<Numeric>> mat() const {return _mat; }
vector<Numeric> &operator[](int i) { return _mat[i]; }
Numeric &operator() (int i, int j) { return _mat[i][j]; }
Matrix<Numeric> &operator=(Matrix<Numeric> x) {
this->_mat = x.mat();
return *this;
}
Matrix<Numeric> operator+(Matrix<Numeric> &x) {
if (this->col() != x.col() || this->row() != x.row()) {
cout << "matrices are different sizes .. ";
this->size(false); cout << "+"; x.size(true);
exit(0);
}
Matrix<Numeric> ret(this->col(), this->row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
ret[i][j] = _mat[i][j] + x[i][j];
if (usingModulo) ret[i][j] %= modulo;
}
}
return ret;
}
Matrix<Numeric> &operator+=(Matrix<Numeric> &x) {
if (this->col() != x.col() || this->row() != x.row()) {
cout << "matrices are different sizes .. ";
this->size(false); cout << "+"; x.size(true);
exit(0);
}
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
_mat[i][j] += x[i][j];
if (usingModulo) _mat[i][j] %= modulo;
}
}
return *this;
}
Matrix<Numeric> operator-(Matrix<Numeric> &x) {
if (this->col() != x.col() || this->row() != x.row()) {
cout << "matrices are different sizes .. ";
this->size(false); cout << "-"; x.size(true);
exit(0);
}
Matrix<Numeric> ret(this->col(), this->row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
ret[i][j] = _mat[i][j] - x[i][j];
if (usingModulo) ret[i][j] %= modulo;
}
}
return ret;
}
Matrix<Numeric> &operator-=(Matrix<Numeric> &x) {
if (this->col() != x.col() || this->row() != x.row()) {
cout << "matrices are different sizes .. ";
this->size(false); cout << "-"; x.size(true);
exit(0);
}
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
_mat[i][j] -= x[i][j];
if (usingModulo) _mat[i][j] %= modulo;
}
}
return *this;
}
Matrix<Numeric> operator*(Matrix<Numeric> &x) {
if (this->row() != x.col()) {
cout << "cannot multiply matrices .. ";
this->size(false); cout << "*"; x.size(true);
exit(0);
}
Matrix<Numeric> ret(this->col(), x.row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < x.row(); ++j) {
for (int k = 0; k < this->row(); ++k) {
ret[i][j] += _mat[i][k] * x[k][j];
if (usingModulo) ret[i][j] %= modulo;
}
}
}
return ret;
}
Matrix<Numeric> &operator*(Numeric k) {
Matrix<Numeric> ret(this->col(), this->row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
ret(i, j) = _mat[i][j] * k;
if (usingModulo) ret(i, j) %= modulo;
}
}
return ret;
}
Matrix<Numeric> &operator*=(Matrix<Numeric> &x) {
if (this->row() != x.col()) {
cout << "cannot multiply matrices .. ";
this->size(false); cout << "*"; x.size(true);
exit(0);
}
Matrix<Numeric> ret(this->col(), x.row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < x.row(); ++j) {
for (int k = 0; k < this->row(); ++k) {
ret[i][j] += _mat[i][k] * x[k][j];
if (usingModulo) ret[i][j] %= modulo;
}
}
}
this->resize(this->col(), x.row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < x.row(); ++j) {
_mat[i][j] = ret[i][j];
}
}
return *this;
}
Matrix<Numeric> &operator*=(Numeric k) {
Matrix<Numeric> ret(this->col(), this->row());
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
_mat[i][j] *= k;
if (usingModulo) _mat %= modulo;
}
}
return *this;
}
Numeric sum() {
Numeric ret = 0;
for (int i = 0; i < this->col(); ++i) {
for (int j = 0; j < this->row(); ++j) {
ret += _mat[i][j];
if (usingModulo) ret %= modulo;
}
}
return ret;
}
void print() {
cout << "-- print "; this->size(false); cout << " --" << endl;
for (int i = 0; i < _col; ++i) {
for (int j = 0; j < _row; ++j) {
if (j != 0) cout << "\t";
cout << _mat[i][j];
}
cout << endl;
}
cout << "------------------" << endl;
}
void print(string str) {
cout << "-- print \"" << str << "\" "; this->size(false); cout << " --" << endl;
for (int i = 0; i < _col; ++i) {
for (int j = 0; j < _row; ++j) {
if (j != 0) cout << "\t";
cout << _mat[i][j];
}
cout << endl;
}
cout << "------------------" << endl;
}
void size (bool endline = true) const {
cout << "(" << this->col() << ", " << this->row() << ")";
if (endline) cout << endl;
}
};
template<class Numeric> class SquareMatrix : public Matrix<Numeric> {
private:
public:
SquareMatrix(int col): Matrix<Numeric>(col, col){
}
SquareMatrix(int col, int num): Matrix<Numeric>(col, col, num) {
}
SquareMatrix(int col, bool identity): Matrix<Numeric>(col, col) {
if (identity) {
for (int i = 0; i < col; ++i) {
this->_mat[i][i] = 1;
}
}
}
};
/*
int main(){
int n; long long k; cin >> n >> k;
Matrix<long long> ans(n, 1, 1), a(n, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
while (k) {
if (k & 1) {
ans = a * ans;
}
a *= a;
k /= 2;
}
cout << ans.sum() << endl;
return 0;
}
*/
int main() {
long long n; cin >> n;
if (n < 8) {
cout << 1;
for (int i = 0; i < n; i++) {
cout << 3;
}
cout << endl;
return 0;
}
Matrix<long long> a(2, 2, 0), b(2, 2, 0), c(2, 1);
a[0][0] = a[0][1] = 1;
a[1][1] = 10;
c[0][0] = 1; c[1][0] = 10;
b = a;
long long ans = 0;
long long k = n-2;
while (k) {
if (k & 1) {
c = a * c;
}
a *= a;
k /= 2;
}
ans += c.sum() * 2 % mod;
c = b * c;
ans = (ans + c.sum()) % mod;
cout << ans << endl;
return 0;
}