[Delirium]

Prof, тебе нужна теория или что?

[lxa85]

слаживание »

Сложение двух чисел, по определению, дает +1 разряд в лучшем случае, вполне укладывающимся в разряд переноса.
Или арифметика сложения на матрицах "длиннее" обычной?
Ну это так, пальцем в небо.
Prof, еще раз четко и внятно напиши, что тебе надо? Желательно с примером, а то по коротким фразам гадать можно долго.

[Prof]

Ребята, простите за такой вопрос. Сам понимаю что написал бред просто заходил с телефона, спешил и небыло при себе примера.
И так, нормальный вопрос:
Есть такая программка:

Код:

#include<stdafx.h>
#include<iostream>
#include<vector>
#include<fstream>
#define dvec vector<vector<int> > 
using namespace std;
dvec mul(dvec a, dvec b) //умножение матриц
{
 dvec ans (a.size(),vector<int>(b.size()));
 int tmp = 0;
 for(int i = 0; i<a.size(); ++i)
 {
  for(int j = 0; j<b.size(); ++j)
  {
   for(int k = 0; k<a[0].size(); ++k)
    ans[i][j]+=a[i][k]*b[k][j];
  }
 }
 return ans;
}
int main()
{
 int n,q;
 ifstream inp ("input.dat");
 ofstream out ("output.sol");
 dvec vec(2,vector<int>(2)); //матрица
 vec[0][0] = 0;
 vec[0][1] = vec[1][0] = vec[1][1] = 1;
 dvec mnoj = vec;   //таже матрица, будет использована как множитель для возведения в степень
 inp >> q;
 n = q-3;
 for(int i = 0; i<n; ++i) //возведение в степень
 {
  vec = mul(vec,mnoj);
 }
 out<<(vec[1][0]+vec[1][1])<<"\n";
 return 0;
}

Суть её в том чтоб считать 30к+ число фибоначчи менее чем за секунду, но для этого нужно переделать её под длинную арифметику и заменить возведения матриц в степень на бинарное возведение в степень. Сам недавно начал учить C++, так что со своими знаниями ещё не до конца понимаю как это реализовать.