結果

問題 No.492 IOI数列
ユーザー le_panda_noir
提出日時 2020-04-11 14:24:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,637 bytes
コンパイル時間 1,411 ms
コンパイル使用メモリ 79,008 KB
最終ジャッジ日時 2025-01-09 17:21:45
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 10
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
template<class T>using vv = vector<vector<T>>;
#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)
template<int MOD> struct MInt {
long long val;
MInt(long long val = 0) : val(val % MOD) { if (val < 0) val += MOD; }
MInt operator-() const { return MInt(-val); }
MInt operator+(const MInt& n) const { return MInt(val) += n; }
MInt operator-(const MInt& n) const { return MInt(val) -= n; }
MInt operator*(const MInt& n) const { return MInt(val) *= n; }
MInt operator/(const MInt& n) const { return MInt(val) /= n; }
MInt& operator+=(const MInt& n) { val = (val + n.val) % MOD; return *this; }
MInt& operator-=(const MInt& n) { val = (MOD + val - n.val) % MOD; return *this; }
MInt& operator*=(const MInt& n) { val = (val * n.val) % MOD; return *this; }
MInt& operator/=(const MInt& n) { val = (*this * n.inv()).val; return *this; }
bool operator==(const MInt& n) { return val == n.val; }
bool operator!=(const MInt& n) { return val != n.val; }
MInt inv() const {
MInt pow = val, ans = 1;
for (int p = MOD - 2; p > 0; p >>= 1) {
if (p & 1) ans *= pow;
pow *= pow;
}
return ans;
}
friend ostream& operator<<(ostream& os, const MInt& n) { os<<n.val; return os; }
friend istream& operator>>(istream& os, MInt& n) { os>>n.val; return os; }
};
const int MOD = 1e9+7;
using mint = MInt<MOD>;
template<class T> struct Matrix {
vector<vector<T>> val;
Matrix(vector<vector<T>> val = {{1, 0}, {0, 1}}) : val(val) {};
Matrix operator+(const Matrix& n) const { return Matrix(val) += n; }
Matrix operator*(const Matrix& n) const { return Matrix(val) *= n; }
Matrix& operator+=(const Matrix& n) {
val[0][0] += n.val[0][0]; val[0][1] += n.val[0][1]; val[1][0] += n.val[1][0]; val[1][1] += n.val[1][1];
return *this;
}
Matrix& operator*=(const Matrix& n) {
T a = val[0][0] * n.val[0][0] + val[0][1] * n.val[1][0],
b = val[0][0] * n.val[0][1] + val[0][1] * n.val[1][1],
c = val[1][0] * n.val[0][0] + val[1][1] * n.val[1][0],
d = val[1][0] * n.val[0][1] + val[1][1] * n.val[1][1];
val[0][0] = a; val[0][1] = b; val[1][0] = c; val[1][1] = d;
return *this;
}
Matrix pow(ll N) {
Matrix pow = val, ans;
for (ll p = N; p > 0; p >>= 1) {
if (p & 1) ans *= pow;
pow *= pow;
}
return ans;
}
};
int main() {
ll in(N);
Matrix ans = vv<mint>{{100, 1}, {0, 1}};
ans = ans.pow(N-1);
cout << ans.val[0][0] + ans.val[0][1] << endl;
cout << 1;
rep(i, (N-1) % 9) {
cout << "01";
}
cout << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0