結果

問題 No.793 うし数列 2
ユーザー pazzle1230pazzle1230
提出日時 2019-02-22 21:46:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,099 bytes
コンパイル時間 1,846 ms
コンパイル使用メモリ 179,952 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-25 06:59:56
合計ジャッジ時間 2,556 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;
const double eps = 1e-10;
template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}
template<::std::uint_fast64_t mod>
class ModInt{
private:
using value_type = ::std::uint_fast64_t;
value_type n;
public:
ModInt() : n(0) {}
ModInt(value_type n_) : n(n_ % mod) {}
ModInt(const ModInt& m) : n(m.n) {}
template<typename T>
explicit operator T() const { return static_cast<T>(n); }
value_type get() const { return n; }
friend ::std::ostream& operator<<(::std::ostream &os, const ModInt<mod> &a) {
return os << a.n;
}
friend ::std::istream& operator>>(::std::istream &is, ModInt<mod> &a) {
value_type x;
is >> x;
a = ModInt<mod>(x);
return is;
}
bool operator==(const ModInt& m) const { return n == m.n; }
bool operator!=(const ModInt& m) const { return n != m.n; }
ModInt& operator*=(const ModInt& m){ n = n * m.n % mod; return *this; }
ModInt pow(value_type b) const{
ModInt ans = 1, m = ModInt(*this);
while(b){
if(b & 1) ans *= m;
m *= m;
b >>= 1;
}
return ans;
}
ModInt inv() const { return (*this).pow(mod-2); }
ModInt& operator+=(const ModInt& m){ n += m.n; n = (n < mod ? n : n - mod); return *this; }
ModInt& operator-=(const ModInt& m){ n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
ModInt& operator/=(const ModInt& m){ *this *= m.inv(); return *this; }
ModInt operator+(const ModInt& m) const { return ModInt(*this) += m; }
ModInt operator-(const ModInt& m) const { return ModInt(*this) -= m; }
ModInt operator*(const ModInt& m) const { return ModInt(*this) *= m; }
ModInt operator/(const ModInt& m) const { return ModInt(*this) /= m; }
ModInt& operator++(){ n += 1; return *this; }
ModInt& operator--(){ n -= 1; return *this; }
ModInt operator++(int){
ModInt old(n);
n += 1;
return old;
}
ModInt operator--(int){
ModInt old(n);
n -= 1;
return old;
}
ModInt operator-() const { return ModInt(mod-n); }
};
template<typename T>
class Matrix{
private:
using size_type = ::std::size_t;
using Row = ::std::vector<T>;
using Mat = ::std::vector<Row>;
size_type R, C; // row, column
Mat A;
void add_row_to_another(size_type r1, size_type r2, const T k){ // Row(r1) += Row(r2)*k
for(size_type i = 0;i < C;i++)
A[r1][i] += A[r2][i]*k;
}
void scalar_multiply(size_type r, const T k){
for(size_type i = 0;i < C;i++)
A[r][i] *= k;
}
void scalar_division(size_type r, const T k){
for(size_type i = 0;i < C;i++)
A[r][i] /= k;
}
public:
Matrix(){}
Matrix(size_type r, size_type c) : R(r), C(c), A(r, Row(c)) {}
Matrix(const Mat &m) : R(m.size()), C(m[0].size()), A(m) {}
Matrix(const Mat &&m) : R(m.size()), C(m[0].size()), A(m) {}
Matrix(const Matrix<T> &m) : R(m.R), C(m.C), A(m.A) {}
Matrix(const Matrix<T> &&m) : R(m.R), C(m.C), A(m.A) {}
Matrix<T> &operator=(const Matrix<T> &m){
R = m.R; C = m.C; A = m.A;
return *this;
}
Matrix<T> &operator=(const Matrix<T> &&m){
R = m.R; C = m.C; A = m.A;
return *this;
}
static Matrix I(const size_type N){
Matrix m(N, N);
for(size_type i = 0;i < N;i++) m[i][i] = 1;
return m;
}
const Row& operator[](size_type k) const& { return A.at(k); }
Row& operator[](size_type k) & { return A.at(k); }
Row operator[](size_type k) const&& { return ::std::move(A.at(k)); }
size_type row() const { return R; } // the number of rows
size_type column() const { return C; }
T determinant(){
assert(R == C);
Mat tmp = A;
T res = 1;
for(size_type i = 0;i < R;i++){
for(size_type j = i;j < R;j++){ // satisfy A[i][i] > 0
if (A[j][i] != 0) {
if (i != j) res *= -1;
swap(A[j], A[i]);
break;
}
}
if (A[i][i] == 0) return 0;
res *= A[i][i];
scalar_division(i, A[i][i]);
for(size_type j = i+1;j < R;j++){
add_row_to_another(j, i, -A[j][i]);
}
}
swap(tmp, A);
return res;
}
Matrix inverse(){
assert(R == C);
assert(determinant() != 0);
Matrix inv(Matrix::I(R)), tmp(*this);
for(size_type i = 0;i < R;i++){
for(size_type j = i;j < R;j++){
if (A[j][i] != 0) {
swap(A[j], A[i]);
swap(inv[j], inv[i]);
break;
}
}
inv.scalar_division(i, A[i][i]);
scalar_division(i, A[i][i]);
for(size_type j = 0;j < R;j++){
if(i == j) continue;
inv.add_row_to_another(j, i, -A[j][i]);
add_row_to_another(j, i, -A[j][i]);
}
}
(*this) = tmp;
return inv;
}
Matrix& operator+=(const Matrix &B){
assert(column() == B.column() && row() == B.row());
for(size_type i = 0;i < R;i++)
for(size_type j = 0;j < C;j++)
(*this)[i][j] += B[i][j];
return *this;
}
Matrix& operator-=(const Matrix &B){
assert(column() == B.column() && row() == B.row());
for(size_type i = 0;i < R;i++)
for(size_type j = 0;j < C;j++)
(*this)[i][j] -= B[i][j];
return *this;
}
Matrix& operator*=(const Matrix &B){
assert(column() == B.row());
Matrix M(R, B.column());
for(size_type i = 0;i < R;i++) {
for(size_type j = 0;j < B.column();j++) {
M[i][j] = 0;
for(size_type k = 0;k < C;k++) {
M[i][j] += (*this)[i][k] * B[k][j];
}
}
}
swap(M, *this);
return *this;
}
Matrix& operator/=(const Matrix &B){
assert(C == B.row());
Matrix M(B);
(*this) *= M.inverse();
return *this;
}
Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }
Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }
Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }
Matrix operator/(const Matrix &B) const { return (Matrix(*this) /= B); }
bool operator==(const Matrix &B) const {
if (column() != B.column() || row() != B.row()) return false;
for(size_type i = 0;i < row();i++)
for(size_type j = 0;j < column();j++)
if ((*this)[i][j] != B[i][j]) return false;
return true;
}
bool operator!=(const Matrix &B) const { return !((*this) == B); }
Matrix pow(size_type k){
assert(R == C);
Matrix M(Matrix::I(R));
while(k){
if (k & 1) M *= (*this);
k >>= 1;
(*this) *= (*this);
}
A.swap(M.A);
return *this;
}
friend ::std::ostream &operator<<(::std::ostream &os, Matrix &p){
for(size_type i = 0;i < p.row();i++){
for(size_type j = 0;j < p.column();j++){
os << p[i][j] << " ";
}
os << ::std::endl;
}
return os;
}
};
const int64 mod = 1e9+7;
using Mint = ModInt<mod>;
using Mat = Matrix<ModInt<mod>>;
int main(void){
cin.tie(0);
ios::sync_with_stdio(false);
vector<vector<Mint>> aa = {{10, 3}, {0, 1}};
vector<vector<Mint>> bb = {{1}, {1}};
Mat a(aa), b(bb);
int64 N;
cin >> N;
a.pow(N);
Mat c = a * b;
cout << c[0][0] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0