Submission #9807

#	Time	Username	Problem	Language	Result	Execution time	Memory
9807		maniac	Phibonacci (kriii2_P)	C++98	0 / 4	0 ms	1092 KiB

P

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define SIZE    1000
using namespace std;
//Addition
void add(char *a, char *b, char *r, int lenA, int lenB, int &lenR){
    reverse(a,a+lenA);
    reverse(b,b+lenB);
    int x,y,i,j,carry;
    for(i=j=lenR=carry=0;i<lenA || j<lenB || carry; i++,j++,lenR++){
        x = (i<lenA)?a[i]-'0':0;
        y = (j<lenB)?b[j]-'0':0;
        r[lenR] = (x+y+carry)%10+'0';  //Here M =10 is base.
        carry = (x+y+carry)/10;     //We can use any base
    }
    r[lenR] = 0;
    reverse(r,r+lenR);
}
//Subtraction with sign handling a>b or b>a
int com(char *a, char *b){
    int lenA = strlen(a);
    int lenB = strlen(b);
    if(lenA>lenB)return 1;
    else if(lenA<lenB)return 2;
    else {
        int i;
        for(i=0;i<lenA;i++){
            if(a[i]>b[i])return 1;
            if(a[i]<b[i])return 2;
        }
    }
    return 0;
}
void sub(char *a, char *b, char *r, int lenA, int lenB, int &lenR){
    bool flag = true;
    char temp[SIZE];
    int t;
    if(com(a,b)==2){
        strcpy(temp,a);
        strcpy(a,b);
        strcpy(b,temp);
        t = lenA;
        lenA = lenB;
        lenB = t;
        flag = false;
    }
    else if(com(a,b)==0){
        strcpy(r,"0");
        return;
    }
    reverse(a,a+lenA);
    reverse(b,b+lenB);
    int x,y,i,j,carry;
    for(i=j=lenR=carry=0;j<lenB || i<lenA || carry; i++,j++,lenR++){
        x = (i<lenA)?a[i]-'0':0;
        y = (j<lenB)?b[j]-'0':0;
        y += carry;
        if(y>x){
            r[lenR] = (10+x-y)%10+'0';
            carry = (10+x)/10;
        }
        else {
            r[lenR] = (x-y)%10+'0';  //Here M =10 is base.
            carry = x/10;     //We can use any base
        }
    }
    while(r[lenR-1]=='0')lenR--;
    if(!flag)r[lenR++] = '-';
    r[lenR] = 0;
    reverse(r,r+lenR);
    reverse(a,a+lenA);
}
//Multiplication
void multiply(char *a, char *r, int lenA, int &lenR, int m) {
    reverse(a,a+lenA);
    int x,i,carry;
    for(i=lenR=carry=0;i<lenA || carry; i++,lenR++){
        x = (i<lenA)?a[i]-'0':0;
        r[lenR] = (x*m+carry)%10+'0';  //Here M =10 is base.  carry = (x*m+carry)/10;     //We can use any base
    }
    r[lenR] = 0;
    reverse(r,r+lenR);
    reverse(a,a+lenA);
}

void multiply(char *a, char *b, char *r, int lenA, int lenB, int &lenR) {
        for (int j = 0; j < lenB; j++) {
                char tmp[SIZE] = {}, tmp2[SIZE] = {};
                int tmpLen = 0, tmp2Len = 0;
                multiply(a, tmp, lenA, tmpLen, b[j] - '0');
                for (int k = tmpLen; k < (lenB-1-j)+tmpLen; k++) tmp[k] = '0';
                tmpLen += (lenB-1-j); tmp[tmpLen] = 0;
                add(tmp, r, tmp2, tmpLen, lenR, tmp2Len);
                strcpy(r, tmp2);
                lenR = strlen(r);
        }
}
//Division
void div(char *a,int lenA, char *r, int& k, int m){
    int mod=0;
    k=0;
    int i;
    for(i=0;i<lenA;i++){
        r[k++] = ((mod*10+a[i]-'0')/m)+'0';
        mod = ((mod*10+a[i]-'0')%m);
    }
    r[k] = 0;
    i = 0;
    int j = 0;
    while(r[i]=='0')i++;
        while (r[k-1] < '0' || r[k-1] > '9') --k;
    for(;i<k;i++,j++)r[j] = r[i];
    r[j]=0;
}
//Mod
int mod(char *a, int lenA, int m){
    int i,mod = 0;
    for(i=0;i<lenA;i++){
        mod = (mod*10+a[i]-'0')%m;
    }
    return mod;
}

//Big Integer POWER a^b SIZE=1000000
void power(char *a, char *result, int lenA, int &lenR,int b){
    int index,x,i,carry;;
    long long int m = atoll(a);
    for(index = 0;index<b-1;index++){
        reverse(a,a+lenA);
        for(i=lenR=carry=0;i<lenA || carry; i++,lenR++){
            x = (i<lenA)?a[i]-'0':0;
            result[lenR] = (x*m+carry)%10+'0';  //Here M =10 is base.
            carry = (x*m+carry)/10;     //We can use any base
        }
        result[lenR] = 0;
        reverse(result,result+lenR);
        strcpy(a,result);
        lenA = strlen(a);
    }
}

const long long MOD(1000000007);

typedef struct matrix{
    long long d[2][2];
}Matrix;

Matrix F={1, 1, 1, 0};

Matrix m_Mul(Matrix A, Matrix B){
    Matrix C;
    C.d[0][0]=(A.d[0][0]*B.d[0][0]+A.d[0][1]*B.d[1][0])%MOD;
    C.d[0][1]=(A.d[0][0]*B.d[1][0]+A.d[0][1]*B.d[1][1])%MOD;
    C.d[1][0]=(A.d[1][0]*B.d[0][0]+A.d[1][1]*B.d[1][0])%MOD;
    C.d[1][1]=(A.d[1][0]*B.d[1][0]+A.d[1][1]*B.d[1][1])%MOD;
    return C;
}

Matrix _m_Power(Matrix A, long long n){
        Matrix Exp = A, Ret = {1, 0, 0, 1};
    while (n > 0) {
                if (n % 2) Ret = m_Mul(Ret, Exp);
                n /= 2;
        Exp = m_Mul(Exp, Exp);
    }
    return Ret;
}

Matrix m_Power(Matrix A, char* n, int nLen) {
        char tmpN[SIZE] = "";
        int tmpLen = 0;

        Matrix Exp = A, Ret = {1, 0, 0, 1};
    while (nLen > 1 || n[nLen-1] > '0') {
                //for (int i = 0; i < nLen; i++) printf("%c", n[i]); puts(""); getchar();
                if ((n[nLen-1] - '0') % 2) Ret = m_Mul(Ret, Exp);
                div(n, nLen, tmpN, tmpLen, 2);
                strcpy(n, tmpN);
                nLen = tmpLen;
        Exp = m_Mul(Exp, Exp);
    }
    return Ret;
}

int main(void)
{

        char a[SIZE], b[SIZE], c[SIZE], one[SIZE] = "1";
        scanf("%s%s", a, c);

    int lenA = strlen(a);
    int lenB = strlen(b);
        int lenC = strlen(c);
        int lenO = 1;

        long long n = atoll(a),
                          m = atoll(c);

    if (n == 0 || m == 0) {
        puts("0 1");
        return 0;
    } else if (n == 1) {
        puts("1 0");
        return 0;
    }

    Matrix A={1, 1, 1, 0}, B={1, 1, 1, 0};
    multiply(a, c, b, lenA, lenC, lenB);
        //printf("%s*%s=%s", a, c, b);puts("");
        strcpy(a, b);
        lenA = lenB;
    A=m_Power(A, b, lenB);
        sub(a, one, c, lenA, lenO, lenC);
    B=m_Power(B, c, lenC);
    printf("%lld %lld\n", A.d[0][1], B.d[0][1]);

    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 3