結果
問題 | No.344 ある無理数の累乗 |
ユーザー |
|
提出日時 | 2016-02-25 14:44:07 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,657 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 61,636 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-22 13:41:21 |
合計ジャッジ時間 | 1,438 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <iostream> #include <vector> class Matrix { public: Matrix() :vector(4) {}; Matrix(const std::vector<int> &vec) :vector(vec) {}; Matrix operator*(const Matrix &right) const { Matrix res; res.vector.at(0) = (vector.at(0) * right.vector.at(0) + vector.at(1) * right.vector.at(2)) % 1000; res.vector.at(1) = (vector.at(0) * right.vector.at(1) + vector.at(1) * right.vector.at(3)) % 1000; res.vector.at(2) = (vector.at(2) * right.vector.at(0) + vector.at(3) * right.vector.at(2)) % 1000; res.vector.at(3) = (vector.at(2) * right.vector.at(1) + vector.at(3) * right.vector.at(3)) % 1000; return std::move(res); } void dot(const Matrix &right) { int a{ (vector.at(0) * right.vector.at(0) + vector.at(1) * right.vector.at(2)) % 1000 }, b{ (vector.at(0) * right.vector.at(1) + vector.at(1) * right.vector.at(3)) % 1000 }, c{ (vector.at(2) * right.vector.at(0) + vector.at(3) * right.vector.at(2)) % 1000 }, d{ (vector.at(2) * right.vector.at(1) + vector.at(3) * right.vector.at(3)) % 1000 }; vector.at(0) = std::move(a); vector.at(1) = std::move(b); vector.at(2) = std::move(c); vector.at(3) = std::move(d); } int at(const int &n) const { return vector.at(n); } private: std::vector<int> vector; }; int a(const int &n) { int i = 0; while ((1 << ++i) < n) { } Matrix res({ 1, 0, 0, 1 }); Matrix mul({ 0, 1, 2, 2 }); while (i >= 0) { res.dot(res); if (((1 << i--) & n) != 0) { res.dot(mul); } } auto result = (res.at(0) + res.at(1)) * 2; if ((n & 1) == 0) { return (result + 999) % 1000; } else { return result % 1000; } } int main() { int n; std::cin >> n; std::cout << a(n) << std::endl; return 0; }