結果
問題 | No.492 IOI数列 |
ユーザー |
![]() |
提出日時 | 2020-06-05 00:25:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 5,330 bytes |
コンパイル時間 | 1,443 ms |
コンパイル使用メモリ | 166,216 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 21:05:38 |
合計ジャッジ時間 | 2,470 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.05 00:25:12**/#include "bits/stdc++.h"using namespace std;typedef long long ll;constexpr int MOD = 1e9 + 7;struct mint {private:long long x;public:mint(long long x = 0) : x((MOD + x) % MOD) {}mint(std::string &s) {long long z = 0;for (int i = 0; i < s.size(); i++) {z *= 10;z += s[i] - '0';z %= MOD;}this->x = z;}mint &operator+=(const mint &a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint &operator-=(const mint &a) {if ((x += MOD - a.x) >= MOD) x -= MOD;return *this;}mint &operator*=(const mint &a) {(x *= a.x) %= MOD;return *this;}mint &operator/=(const mint &a) {long long n = MOD - 2;mint u = 1, b = a;while (n > 0) {if (n & 1) {u *= b;}b *= b;n >>= 1;}return *this *= u;}mint operator+(const mint &a) const {mint res(*this);return res += a;}mint operator-(const mint &a) const {mint res(*this);return res -= a;}mint operator*(const mint &a) const {mint res(*this);return res *= a;}mint operator/(const mint &a) const {mint res(*this);return res /= a;}friend std::ostream &operator<<(std::ostream &os, const mint &n) {return os << n.x;}bool operator==(const mint &a) const {return this->x == a.x;}};template < class T >struct Matrix {std::vector< std::vector< T > > A;Matrix() {}Matrix(size_t n, size_t m) : A(n, std::vector< T >(m, 0)) {}Matrix(size_t n) : A(n, std::vector< T >(n, 0)){};size_t height() const {return (A.size());}size_t width() const {return (A[0].size());}inline const std::vector< T > &operator[](int k) const {return (A.at(k));}inline std::vector< T > &operator[](int k) {return (A.at(k));}static Matrix I(size_t n) {Matrix mat(n);for (int i = 0; i < n; i++) mat[i][i] = 1;return (mat);}Matrix &operator+=(const Matrix &B) {size_t n = height(), m = width();assert(n == B.height() && m == B.width());for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j];return (*this);}Matrix &operator-=(const Matrix &B) {size_t n = height(), m = width();assert(n == B.height() && m == B.width());for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j];return (*this);}Matrix &operator*=(const Matrix &B) {size_t n = height(), m = B.width(), p = width();assert(p == B.height());std::vector< std::vector< T > > C(n, std::vector< T >(m, 0));for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)for (int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);A.swap(C);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);}friend std::ostream &operator<<(std::ostream &os, Matrix &p) {size_t n = p.height(), m = p.width();for (int i = 0; i < n; i++) {os << "[";for (int j = 0; j < m; j++) {os << p[i][j] << (j + 1 == m ? "]\n" : ",");}}return (os);}T determinant() {Matrix B(*this);assert(width() == height());T ret = 1;for (int i = 0; i < width(); i++) {int idx = -1;for (int j = i; j < width(); j++) {if (B[j][i] != 0) idx = j;}if (idx == -1) return (0);if (i != idx) {ret *= -1;swap(B[i], B[idx]);}ret *= B[i][i];T vv = B[i][i];for (int j = 0; j < width(); j++) {B[i][j] /= vv;}for (int j = i + 1; j < width(); j++) {T a = B[j][i];for (int k = 0; k < width(); k++) {B[j][k] -= B[i][k] * a;}}}return (ret);}Matrix pow(ll k) const {auto res = I(A.size());auto M = *this;while (k > 0) {if (k & 1) {res *= M;}M *= M;k >>= 1;}return res;}};int main() {ll n;cin >> n;Matrix< mint > mat(2);mat.A[0][0] = 100;mat.A[0][1] = 1;mat.A[1][0] = 0;mat.A[1][1] = 1;auto p = mat.pow(n - 1);cout << p.A[0][0] + p.A[0][1] << endl;for (int i = 0; i < n % 11 - 1; i++) {cout << 10;}if (n % 11 == 0) {cout << 0 << endl;} else {cout << 1 << endl;}return 0;}