結果
| 問題 | No.303 割れません |
| ユーザー |
 kei
|
| 提出日時 | 2018-10-08 19:14:32 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 9,003 bytes |
| コンパイル時間 | 2,737 ms |
| コンパイル使用メモリ | 191,500 KB |
| 実行使用メモリ | 754,520 KB |
| 最終ジャッジ日時 | 2024-10-12 15:22:03 |
| 合計ジャッジ時間 | 14,098 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,824 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | MLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
ソースコード
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
/*
<url:https://yukicoder.me/problems/no/303>
問題文============================================================
=================================================================
解説=============================================================
================================================================
*/
class bigint {
private:
static const int BASE = 100000000, LEN = 32;
bool negative;
std::vector<int> a;
bigint& normalize();
public:
bigint(int x = 0);
bigint(const std::string& s);
bigint& operator = (const bigint& x);
bigint& operator = (int x);
bigint& operator = (const std::string& s);
const bool operator < (const bigint& x) const;
const bool operator > (const bigint& x) const;
const bool operator <= (const bigint& x) const;
const bool operator >= (const bigint& x) const;
const bool operator != (const bigint& x) const;
const bool operator == (const bigint& x) const;
bigint operator -() const;
bigint& operator += (const bigint& x);
bigint& operator -= (const bigint& x);
bigint& operator *= (const bigint& x);
bigint& operator /= (const bigint& x);
bigint& operator %= (const bigint& x);
const bigint operator + (const bigint& x) const;
const bigint operator - (const bigint& x) const;
const bigint operator * (const bigint& x) const;
const bigint operator / (const bigint& x) const;
const bigint operator % (const bigint& x) const;
friend std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs);
friend std::istream& operator >> (std::ostream& is, bigint& x); //適当実装
friend std::ostream& operator << (std::ostream& os, const bigint& x);
friend const bigint abs(bigint x);
};
bigint& bigint::normalize() {
int i = a.size()-1;
while (i >= 0 && a[i] == 0) --i;
a.resize(i+1);
if (a.size() == 0) negative = false;
return *this;
}
bigint::bigint(int x) : negative(x<0) {
x = abs(x);
for (; x > 0; x /= BASE) a.push_back(x % BASE);
}
bigint::bigint(const std::string& s): negative(false) {
int p = 0;
if (s[p] == '-') { ++p; negative = true; }
else if (s[p] == '+') { ++p; }
for (int i = s.size()-1, v = BASE; i >= p; --i, v*=10) {
int x = s[i]-'0';
if (x < 0 || 9 < x) {
std::cerr<<"error: parse error:"<<s<<std::endl;
exit(1);
}
if (v == BASE) {
v = 1;
a.push_back(x);
} else a.back() += (x)*v;
}
normalize();
}
bigint& bigint::operator = (const bigint& x) {
negative = x.negative;
a = x.a;
return *this;
}
bigint& bigint::operator = (int x) { return *this = bigint(x); }
bigint& bigint::operator = (const std::string& s) { return *this = bigint(s); }
const bool bigint::operator < (const bigint& x) const {
if (negative != x.negative) return negative < x.negative;
if (a.size() != x.a.size()) return (a.size() < x.a.size())^negative;
for(int i = a.size()-1; i >= 0; --i)
if (a[i] != x.a[i]) return (a[i] < x.a[i])^negative;
return false;
}
const bool bigint::operator > (const bigint& x) const { return x<(*this); }
const bool bigint::operator <= (const bigint& x) const { return !(x<(*this)); }
const bool bigint::operator >= (const bigint& x) const { return !((*this)<x); }
const bool bigint::operator != (const bigint& x) const { return (*this)<x || x<(*this); }
const bool bigint::operator == (const bigint& x) const { return !((*this)<x || x<(*this)); }
bigint bigint::operator -() const {
bigint ret(*this);
if (a.size()) ret.negative = !ret.negative;
return ret;
}
bigint& bigint::operator += (const bigint& x) {
if (negative != x.negative) return *this -= -x;
if (a.size() < x.a.size()) a.resize(x.a.size());
int tmp = 0;
for (int i = 0; i < a.size(); ++i) {
a[i] += (i<x.a.size()?x.a[i]:0) + tmp;
tmp = a[i] / BASE;
a[i] %= BASE;
}
if (tmp) a.push_back(1);
return *this;
}
bigint& bigint::operator -= (const bigint& x) {
if (negative != x.negative) return *this += -x;
std::vector<int> b(x.a);
if ((*this < x) ^ negative) {
a.swap(b);
negative = !negative;
}
for (int i = 0, tmp = 0; i < a.size(); ++i) {
a[i] += BASE - (i<b.size()?b[i]:0) + tmp;
tmp = a[i] / BASE - 1;
a[i] %= BASE;
}
return this->normalize();
}
bigint& bigint::operator *= (const bigint& x) {
negative ^= x.negative;
std::vector<int> c(a.size()*x.a.size()+1);
for (int i = 0; i < a.size(); ++i) {
long long tmp = 0;
for (int j = 0; j < x.a.size(); ++j) {
long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp;
tmp = v / BASE;
c[i+j] = (int)(v % BASE);
}
if (tmp) c[i+x.a.size()] += (int)tmp;
}
a.swap(c);
return this->normalize();
}
bigint& bigint::operator /= (const bigint& x) {
return *this = divmod(*this,x).first;
}
bigint& bigint::operator %= (const bigint& x) {
return *this = divmod(*this,x).second;
}
const bigint bigint::operator + (const bigint& x) const {
bigint res(*this); return res += x;
}
const bigint bigint::operator - (const bigint& x) const {
bigint res(*this); return res -= x;
}
const bigint bigint::operator * (const bigint& x) const {
bigint res(*this); return res *= x;
}
const bigint bigint::operator / (const bigint& x) const {
bigint res(*this); return res /= x;
}
const bigint bigint::operator % (const bigint& x) const {
bigint res(*this); return res %= x;
}
std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs) {
if (!rhs.a.size()) {
std::cerr<<"error: division by zero"<<std::endl;
exit(1);
}
bigint x(abs(rhs)), q, r;
for (int i = lhs.a.size()-1; i >= 0; --i) {
r = r * bigint::BASE + lhs.a[i];
int head = 0, tail = bigint::BASE;
if (r >= x) {
while (head + 1 < tail) {
int mid = (head + tail) / 2;
if (x * bigint(mid) > r) tail = mid;
else head = mid;
}
r -= x * head;
}
q.a.push_back(head);
}
reverse(q.a.begin(), q.a.end());
bool neg = lhs.negative ^ lhs.negative;
q.negative = neg; r.negative = neg;
return std::make_pair(q.normalize(), r.normalize());
}
std::istream& operator >> (std::istream& is, bigint& x) {
std::string tmp; is >> tmp;
x = bigint(tmp);
return is;
}
std::ostream& operator << (std::ostream& os, const bigint& x) {
if (x.negative) os << '-';
if (!x.a.size()) os << 0;
else os << x.a.back();
for (int i = (int)x.a.size()-2; i >= 0; --i) {
os.width(bigint::LEN);
os.fill('0');
os << x.a[i];
}
return os;
}
const bigint abs(bigint x) {
x.negative = false;
return x;
}
typedef vector<bigint> vec;
typedef vector<vec> mat;
/*
行列累乗
X = A^M*B
A ( N*N行列)
O(N^3 logM)
*/
mat mul(mat&A,mat&B){
mat C(A.size(),vec(B[0].size()));
for(int i = 0; i < (int)A.size();i++){
for(int k = 0; k < (int)B.size();k++){
if(A[i][k] == 0) continue;
for(int j = 0; j < B[0].size();j++){
C[i][j] = (C[i][j] + A[i][k]*B[k][j]);
}
}
}
return C;
}
mat pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i = 0; i < A.size();i++){
B[i][i] = 1;
}
while(n > 0){
if(n&1) B= mul(B,A);
A = mul(A,A);
n>>=1;
}
return B;
}
bigint calcfib(ll L){
mat A(2,vec(2,1));
A[1][1] = 0;
return pow(A,L-1)[0][0];
}
void solve(){
ll L; cin >> L;
if(L == 2){
cout << 3 << endl;
cout << "INF" << endl;
return;
}
cout << L << endl;
if(L%2 == 1){
cout << calcfib(L) << endl;
}else{
bigint fib1 = calcfib(L),fib2 = calcfib(L/2);
fib2*=fib2;
cout << (fib1-fib2) << endl;
}
}
int main(void) {
cin.tie(0); ios_base::sync_with_stdio(false);
solve();
return 0;
}