結果
| 問題 |
No.741 AscNumber(Easy)
|
| コンテスト | |
| ユーザー |
 potoooooooo
|
| 提出日時 | 2018-12-12 23:25:17 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 6,356 bytes |
| コンパイル時間 | 1,782 ms |
| コンパイル使用メモリ | 175,412 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-09-25 03:42:48 |
| 合計ジャッジ時間 | 3,296 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 55 |
ソースコード
#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<Numeric> &operator[](int i) { return _mat[i]; }
Numeric &operator() (int i, int j) { return _mat[i][j]; }
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;
}
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; cin >> n;
matrix<long long> ans(1, 10, 0), mat(10, 10, 0);
for (int i = 0; i < 10; ++i) {
for (int j = i; j < 10; ++j) {
mat[i][j] = 1;
}
}
ans[0][0] = 1;
while (n > 0) {
if (n % 2 == 1) {
ans *= mat;
}
n /= 2; mat *= mat;
}
long long sum = 0;
for (int i = 0; i < 10; i++) {
sum += ans[0][i]; sum %= mod;
}
cout << sum << endl;
}