zarif_2002's blog

codeforces round #520 C
By zarif_2002, history, 6 years ago, In English

[problem:banh-me]

what's wrong with this code? please.

include<stdio.h>

include<math.h>

int main(){

long long k,l;

int a,b,i,p,q,j,ara[100003],t;

long long r,s1;

char s[100003];

l = pow(10,9) + 7;

scanf("%d %d\n",&a,&b);

gets(s);

t = 0;

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

    if(s[i] == '1'){

        t++;
    }
    ara[i + 1] = t;
}
for(i = 0; i < b; i++){

    scanf("%d %d",&p,&q);

    s1 = ara[q] - ara[p - 1];

    r = ((long long)q - (long long)p + 1) - s1;

    k = pow(2,r)*((pow(2,s1)) - 1);

    k = k%l;

    printf("%lld\n",k);
}
return 0;

}

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As the power of 2 can be very large (10^5) in this problem, you can't contain it any classical data type. And we only need the power of 2 in this problem, you can store the powers by simply running a loop.

const long long mod=1000000007;
long long pwr[100007];
pwr[0]=1;
for(int i=1;i<100002;i++)pwr[i]=(pwr[i-1]*(long long)2)%mod;

But you should learn about bigmod to find large power of a number.

As, the pow function actually returns a double value, it is wise not use pow function.

→ Reply