結果
問題 | No.492 IOI数列 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}