题目说明是1000000位不是1-1000000
就是最多要处理1000000个数字~

非法操作应该就是说数组越界了

这题可以分3种情况来考虑,如果某数位上的数字是0那么就不用管这个数
如果某数位上的数字是1,那就是sum+=(2^k);--(其中k是表示这个数位所在的位数)
如果某数位上的数字大于1,那后面每个位无论是什么(包括这位)都要归纳为第二种情况处理~

因为数据很大,所以可以每次进行*2或者<<1后和原来的数相加要%1000000007,否则会数据溢出

这题余数很大,对于第三种情况用快速幂对unsigned进行运算很容易溢出(明显题目没有顾及到用快速幂来进行优化这个问题),要另外处理,所以第一种直接算就可以了,对于第二种就是判断处理数位上是否是0就可以了~

好像还是要用到数组来保留信息,因为读取数据的时候是从最低位开始读取的~

但也可以不用数组,但这样就要先知道((2^n)-1)%1000000007的值,然后每遍历一次就进行逆运算,能不能被2整除,如果不能就加1000000007再除以2,如果能就直接除以2就可以了~



另说:
pow到底是个什么函数呢,我竟然不知道那个是怎么用的,这题的pow是用来干嘛的
嗯,看来是我对楼主程序的理解能力有很大问题~

[此贴子已经被作者于2018-5-9 17:29编辑过]

你for循环中间的那个条件是不是错误的，然后算出来了i-1位的由0,1组成数的个数，但是i位的好像没有计.

谢谢大佬，pow就是用来求幂的，后面溢出那里我水平不够没看懂，你是说取模那里不能直接用%1000000007来算么？

[此贴子已经被作者于2018-5-9 16:38编辑过]

我在5楼解释了一下，我觉得方法应该是对的，因为数据输出是对的，只是不知道为什么过不了OJ。

for(i=i-1;i+1;i--)
尝试改成 for(i=i-1;i>=0;i--)试试？

唉,人家都说得这么清楚了

需要用到pow么,可以看看这操作~
for (i=n-1;i!=-1;--i)
{
    s+=sum;
   
    sum*=2;//sum<<1
    if (sum>=k)
        sum-=k;

    if (s>=k)
        s-=k;
}


PS:

还有另一种写法

for (i=sum=0;i!=n;++i)
{
     sum*=2;//sum<<1
     if (sum>=k)
         sum-=k;
}

for (i=0;i!=n;++i)
{
    s+=sum;
    sum=sum%2?sum/2:(sum+k)/2;

    if (s>=k)
        s-=k;
}


pow其实本质也是一个函数,对于处理一个超过double范围的数还是会产生溢出的,因此要另外处理~

[此贴子已经被作者于2018-5-9 17:41编辑过]

这条题目输入和题意似乎有冲突的地方~
输入10
输出2
很明显输入的就是n
但题意说是位数就不知道是怎么回事了~

这里有个关于求位数的代码可以看看,或者还会有bug,但基本没啥问题了~

#include<stdio.h>

unsigned fun( unsigned );

int main( void )
{
    unsigned n;
    
    if (scanf("%u",&n)!=1)
        return 1;
    
    printf("%u\n",fun(n));
    
    return 0;
}

unsigned fun( unsigned n )
{
    const unsigned k=1000000007;
    
    unsigned s=1;
    unsigned sum;
    
    size_t i;
    
    if (n==0)
        return 0;
    
    for (i=1;i!=n;++i)
    {
        s<<=1;
        
        s=(s>=k)?(s-k):(s);
    }
   
    for (i=sum=0;i!=n;++i)
    {
        unsigned t;
        
        if (scanf("%1u",&t)!=1)
            return 0;
            
        if (t)
            sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
         
        if (t>1)
        {
            ++i;
            
            break;
        }
    }
    
    for (;i!=n;++i)
    {
        unsigned t;
        
        if (scanf("%1u",&t)!=1)
            return 0;
            
        sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
    }
    
    return sum;
}

这题大意应该还是要用到数组(预先不说要输入多少个数),那可以这样~

#include<stdio.h>
#include<string.h>

unsigned fun( const char*,size_t );

char str[1000005];

int main( void )
{   
    fgets(str,sizeof (str),stdin);
    
    str[strcspn(str,"\n")]='\0';
    
    printf("%u\n",fun(str,strlen(str)));
    
    return 0;
}

#include<errno.h>

unsigned fun( const char* str,size_t n )
{
    const unsigned k=1000000007;
    
    unsigned s=1;
    unsigned sum;
    
    size_t i;
    
    if (n==0)
        return 0;
    
    for (i=1;i!=n;++i)
    {
        s<<=1;
        
        s=(s>=k)?(s-k):(s);
    }
   
    for (sum=0;*str!='\0';++str)
    {
        unsigned t;
        if (sscanf(str,"%1u",&t)!=1)
        {
            errno=ERANGE;
            
            return 0;
        }
        
        if (t)
            sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
         
        if (t>1)
        {
            ++str;
            
            break;
        }
    }
    
    for (;*str!='\0';++str)
    {
        unsigned t;
        if (sscanf(str,"%1u",&t)!=1)
        {
            errno=ERANGE;
            
            return 0;
        }
            
        sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
    }
    
    return sum;
}

[此贴子已经被作者于2018-5-9 23:01编辑过]

不用数组也预先不知道字符串长度可以这样~

#include<stdio.h>

unsigned fun( void );

int input( unsigned* );

int main( void )
{
    unsigned n;
    
    printf("%u\n",fun());
    
    return 0;
}

int input( unsigned* t )
{
    char s[2]={0,0};
    
    *s=getchar();
    
    return  (*s!='\n')?(sscanf(s,"%1u",t)):(EOF);
}

#include<errno.h>

unsigned fun( void )
{
    const unsigned k=1000000007;
    
    unsigned sum=0;
   
    while (1)
    {
        unsigned t;
        
        const int flag=input(&t);
        
        if (flag==EOF)
            return sum;
        else if (flag!=1)
        {
            errno=ERANGE;
            
            return 0;
        }

        sum=(sum<<1)|(!!t);

        (sum>=k)?(sum-=k):(NULL);
         
        if (t>1)            
            break;
    }
    
    while (1)
    {
        unsigned t;
        
        const int flag=input(&t);
                
        if (flag==EOF)
            break;
        else if (flag!=1)
        {
            errno=ERANGE;
            
            return 0;
        }
            
        sum=(sum<<1)|(1);
        
        (sum>=k)?(sum-=k):(NULL);
    }
    
    return sum;
}

[此贴子已经被作者于2018-5-10 10:38编辑过]