Fibonacci numbers

• Problem Description

  
  "Chef's love for Fibonacci numbers helps him to design following interesting problem.
  He defines a function F for an array S as follows:
  
  where
  Si denotes a non-empty subset of multiset S.
  sum(Si) denotes the sum of all element of multiset Si.
  Fibonacci(x) denotes the xth Fibonacci number.
  Given an array A consisting of N elements. Chef asked you to process following two types of queries on this array accurately and efficiently.
  C X Y: Change the value of Xth element of array to Y i.e AX = Y.
  Q L R: Compute function F over the subarray defined by the elements of array A in the range L to R, both inclusive.
  Please see the Note section if you need details regarding Fibonacci function. 
  Input
  First line of input contains 2 space separated integer N and M denoting the size of array A and the number of queries to be performed. Next line of input contains N space separated integers denoting the elements of array A. Each of next M lines of input contains a query having one of the mentioned two types.
  Output
  For each query of type Q, output the value of function F for the given range of array A.
  "

• CODING ARENA

• #include <stdio.h>

  #define MOD 1000000007

  #define lli long long int

  
  

  lli expo(lli x, lli y) {

    lli z = 1;

    while (y > 0) {

      if (y & 1) z = (z*x)%MOD;

      y = y>>1;

      x = (x*x)%MOD;

    }

    return z;

  }

  
  

  void mul1(lli F[2][2], lli M[2][2]) {

    lli x = (((F[0][0]*M[0][0])%MOD)+((F[0][1]*M[1][0])%MOD))%MOD;

    lli y = (((F[0][0]*M[0][1])%MOD)+((F[0][1]*M[1][1])%MOD))%MOD;

    lli z = (((F[1][0]*M[0][0])%MOD)+((F[1][1]*M[1][0])%MOD))%MOD;

    lli w = (((F[1][0]*M[0][1])%MOD)+((F[1][1]*M[1][1])%MOD))%MOD;

    F[0][0] = x;

    F[0][1] = y;

    F[1][0] = z;

    F[1][1] = w;

  }

  
  

  void pow1(lli F[2][2], lli n) {

    if(n==0 || n==1) return;

    pow1(F, n/2);

    mul1(F, F);

    if (n%2!=0) {

      lli M[2][2] = {{2,4},{1,0}};

      mul1(F, M);

    }

  }

  
  

  void fib1(lli ff[2], int n) {

    if (n == 0) {

      ff[0] = 1;

      ff[1] = 1;

      return;

    }

    if (n == 1) {

      ff[0] = 2;

      ff[1] = 1;

      return;

    }

    lli F[2][2] = {{2,4},{1,0}};

    pow1(F, n);

    //printf("|%lld %lld|\n|%lld %lld|\n", F[0][0], F[0][1], F[1][0], F[1][1]);

    ff[0] = F[0][0];

    ff[1] = F[1][0];

    return;

  }

  
  

  int main(void) {

    int n, m, i,  l, r;

    lli arr[100001], xps[100001], xpd[100002], ff[2];

    lli ch1[100001], ch2[100001], cm1[100002], cm2[100002];

    lli  x, y,  num1, num2, den1, den2, sum;

    char c[9];

  
  

    scanf("%d %d", &n, &m);//n=m=100000;

    for (i=0; i<n; i++) {

      scanf("%lld", &arr[i]);

      //arr[i] = 1000000000;

    }

  
  

    // ch1[0] = 1; ch1[1] = 6; ch1[2] = 16; ch1[3] = 56; ch1[4] = 176;

    // ch2[0] = 1; ch2[1] = 2; ch2[2] = 8; ch2[3] = 24; ch2[4] = 80;

    for (i=0; i<n; i++) {

      fib1(ff, arr[i]);

      xps[i] = expo(2, arr[i]);

      ch1[i] = ((((ff[0]+MOD)-ff[1])%MOD)+xps[i])%MOD;

      ch2[i] = ff[1];

      //printf("[%lld %lld]\n", ch1[i], ch2[i]);

    }

    cm1[0] = 1;

    cm2[0] = 0;

    xpd[0] = 1;

    for (i=1; i<=n; i++) {

      x = ( ((cm1[i-1]*ch1[i-1])%MOD) + (( ((cm2[i-1]*ch2[i-1])%MOD) *5)%MOD) )%MOD;

      y = ( ((cm1[i-1]*ch2[i-1])%MOD) + ((ch1[i-1]*cm2[i-1])%MOD) )%MOD;

      cm1[i] = x;

      cm2[i] = y;

      xpd[i] = (xpd[i-1]*xps[i-1])%MOD;

    }

    // for (i=0; i<=n; i++) {

    //   printf("%lld ", xpd[i]);

    // } printf("\n");

    // for (i=0; i<=n; i++) {

    //   printf("%lld %lld\n", cm1[i], cm2[i]);

    // } printf("\n");

  
  

    while (m--) {

      scanf("%s %d %d", c, &l, &r);//c[0]='Q';l=1;r=n;

      if (c[0]=='C') {

        l--;

        arr[l] = r;

        fib1(ff, r);

        xps[l] = expo(2, r);

        ch1[l] = ((((ff[0]+MOD)-ff[1])%MOD)+xps[l])%MOD;

        ch2[l] = ff[1];

        for (i=1; i<=n; i++) {

          x = ( ((cm1[i-1]*ch1[i-1])%MOD) + (( ((cm2[i-1]*ch2[i-1])%MOD) *5)%MOD) )%MOD;

          y = ( ((cm1[i-1]*ch2[i-1])%MOD) + ((ch1[i-1]*cm2[i-1])%MOD) )%MOD;

          cm1[i] = x;

          cm2[i] = y;

          xpd[i] = (xpd[i-1]*xps[i-1])%MOD;

        }

      } else {

        l--;

        r--;

        /*num1 = ch1[l];

        num2 = ch2[l];

        //printf("[%lld %lld]", num1, num2);

        for (i=l+1; i<=r; i++) {

          x = ( ((num1*ch1[i])%MOD) + (( ((num2*ch2[i])%MOD) *5)%MOD) )%MOD;

          y = ( ((num1*ch2[i])%MOD) + ((ch1[i]*num2)%MOD) )%MOD;

          num1 = x;

          num2 = y;

          //printf("[%lld %lld]", num1, num2);

        }*/

        num1 = (((cm2[r+1]*cm1[l])%MOD)*2)%MOD;

        num2 = ((num1+MOD) - ((((cm1[r+1]*cm2[l])%MOD)*2)%MOD) )%MOD;

        den1 = ((((cm1[l]*cm1[l])%MOD)+MOD) - (((cm2[l]*cm2[l])%MOD)*5)%MOD)%MOD;

        den2 = (((xpd[r+1]*expo(xpd[l],MOD-2))%MOD)*den1)%MOD;

        //num2 = (num2*2)%MOD;

        sum = (num2*expo(den2,MOD-2))%MOD;

        //printf("(%lld %lld %lld)", num2, den, sum);

        printf("%lld\n", sum);

      }

    }

    

    return 0;

  }

• Test Case 1

  
  Input (stdin)

  3 5
  
  1 2 3
  
  Q 1 2
  
  Q 2 3
  
  C 1 2
  
  Q 1 2
  
  Q 1 3
  
  

  Expected Output

  4
  
  8
  
  5
  
  30

• Test Case 2

  
  Input (stdin)

  3 4
  
  3 5 7
  
  Q 1 2
  
  Q 1 3 
  
  C 1 4
  
  Q 2 3
  
  

  Expected Output

  28
  
  850
  
  162