글 읽기 - 피보나치 수 4 (큰수, 행렬 풀이) 질문입니다

gnues 5년 전 0

10000번째 피보나치 수 까지 제대로 나오는 듯 한데 제출시 지속적으로 틀렸다고 나와 질문드립니다.

단순히 덧셈만 이용해서 O(N)만으로 풀었을때는 정답으로 처리되는데,
행렬을 이용해서 좀더 빨리 풀어보려 하니 틀렸다고 뜨고 원인을 모르겠습니다.

행렬 풀이 방식은 피보나치 수 6 문제 (https://www.acmicpc.net/proble...)를 통과한 코드에
타입만 큰 수로 바꾸어 놓은 상태입니다.
큰 수를 처리해주는 num Class를 만들어 덧셈, 곱셈을 정의해주고 사용 했습니다.

제 행렬 풀이 방식으로 구한 10000번 째 피보나치 수는 아래와 같습니다.
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

10000번째 수까지 제대로 나오는 게 맞다면 왜 틀렸다고 뜨는 건지 도통 알수가 없어 고민만 하다 질문글 올려봅니다..
제가 놓친 무언가가 있을까요?

// 피보나치 수 4
// https://www.acmicpc.net/problem/10826
#include<iostream>
#include<vector>
#include<string>
using namespace std;

class num {
private:
  vector<long long> n;
  const static int MAX = (int)1e9;
  const static int MAXLEN = 9;
public:
  num() {}
  num(long long _n) { if(!_n) n.push_back(0); while(_n) { n.push_back(_n%MAX); _n/=MAX; }
  }
  ~num() { n.clear(); }
  const num operator+ (const num& op) const {
    num res;
    int size = n.size(), sizeOP = op.n.size();
    int N = size > sizeOP ? size : sizeOP;
    int carry = 0;
    for(int i=0; i<N; i++) {
      int a = (i<size?n[i]:0) + (i<sizeOP?op.n[i]:0) + carry;
      if(a >= MAX) { carry = 1; a -= MAX; }
      else carry = 0;
      res.n.push_back(a);
    }
    if(carry) res.n.push_back(carry);
    return res;
  }
  const num operator* (const num& op) const {
    num res;
    int size = n.size(), sizeOP = op.n.size();
    const num& b = (size < sizeOP ? op : *this);
    const num& s = (size < sizeOP ? *this : op);
    int bSize = size < sizeOP ? sizeOP : size;
    int sSize = size < sizeOP ? size : sizeOP;
    int resSize = bSize + sSize;
    if(b.n[bSize-1]*s.n[sSize-1] < MAX) resSize--;
    res.n.assign(resSize, 0);
    int carry = 0;
    for(int i=0; i<bSize; i++)
      for(int j=0; j<sSize; j++) {
        long long a = b.n[i] * s.n[j];
        if(a >= MAX) { res.n[i+j+1] += a/MAX; a %= MAX; }
        res.n[i+j] += a;
        if(res.n[i+j]>=MAX) {
          res.n[i+j+1] += res.n[i+j]/MAX;
          res.n[i+j] %= MAX;
        }
      }
    return res;
  }
  void prt() const {
    int size = n.size();
    cout << n[size-1];
    for(int i=size-2; i>=0; i--) {
      string s = to_string(n[i]);
      int z = MAXLEN - s.size();
      while(z--) cout << '0';
      cout << s;
    }
  }
};

typedef vector<vector<num>> Matrix;

Matrix operator * (const Matrix& a, const Matrix& b) {
  int size = a.size();
  Matrix res(size, vector<num>(size,0));
  for(int i=0; i<size; i++)
    for(int j=0; j<size; j++)
      for(int k=0; k<size; k++)
        res[i][j] = res[i][j] + a[i][k] * b[k][j];
  return res;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int n; cin >> n;
  if(n<=1) { cout << n; return 0; }
  Matrix ans = {{1,0},{0,1}};
  Matrix I = {{1,1},{1,0}};
  while(n) {
    if(n&1) ans = ans * I;
    I = I * I;
    n/=2;
  }
  ans[0][1].prt();
  // num a(1), ans(0), t;
  // while(n--) {
  //   t = ans + a;
  //   ans = a;
  //   a = t;
  // }
  // ans.prt();
  return 0;
}

jaehoo1 5년 전 0

0은 넣어보셨나요

gnues 5년 전 0

@jaehoo1 네 넣어보았습니다. 0으로 제대로 출력 되는 것도 확인했습니다.

jaehoo1 5년 전 0

https://ideone.com/qtFZUL
https://ideone.com/xuppp6

저는 잘 모르겠군요..

jaehoo1 5년 전 1

https://ideone.com/CHLWBX

참고로 5000도 안됩니다

gnues 5년 전 0

@jaehoo1 정보 감사합니다.
특정 n에 대해서 에러가 발생하고 있었습니다.

에러는 큰 수를 처리하는 클래스의 operator * 에서 발생하던 문제였습니다.
카라추바 알고리즘을 따로 쓰지않고 쌩으로 곱해서 큰 수 벡터에 넣는 도중에 자리수를 제대로 다뤄주지 않아 생기는 문제였습니다.

도움 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

피보나치 수 4 (큰수, 행렬 풀이) 질문입니다

gnues 5년 전 0

jaehoo1 5년 전 0

gnues 5년 전 0

jaehoo1 5년 전 0

jaehoo1 5년 전 1

gnues 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말