HDU 6304 Chiaki Sequence Revisited

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6304

多校contest1

Problem Description

Chiaki is interested in an infinite sequence a1,a2,a3,..., which is defined as follows:

an={1an−an−1+an−1−an−2n=1,2n≥3

Chiaki would like to know the sum of the first n terms of the sequence, i.e. ∑i=1nai. As this number may be very large, Chiaki is only interested in its remainder modulo (109+7).

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤105), indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤1018).

Output

For each test case, output an integer denoting the answer.

题目大意是求一个奇怪序列的前 n 项和，n最坏情况达 1e18。

开始打了个表，发现在序列是从1开始的连续整数(每个整数出现的次数不同)，除了数字 1是出现两次，其他数字如x 都是出现 lowbit(x)后缀0的个数+1 次。如2(10) 出现2次，3(11) 出现1次，4(100) 出现3次，5(101)出现1次，6(110) 出现2次...

可以发现这是一个十分有特点的(类似2进制，有部分对称性)的序列

接下来我们可以发现如果把1当做出现1次，出现在 2^n 上，如果占满，次数总和刚好是 2^(n+1) -1 次，那么多出来的数似乎又没有规律了，这时我们可以利用局部对称与这个和二进制相似的特点，找到第 n 个数是数字多少(落在图中的位置)，

有两种方法:

第一种可以知道N(自减一后)对应的准确数字，但不知N落在的数字差几次被填满，不便计算。

 void init(){

     P[]=;P[]=;

     nP[]=;nP[]=;

     for(int i=;i<=;++i){

         P[i]=*P[i-];

         nP[i]=P[i]-;

     }

 }

 ll getbound(ll N){

     ll bound=;

     for(int i=;i>=;--i){

         while(N>=nP[i]){

             N-=nP[i];

             bound+=P[i-];

         }

     }

     return bound;

 }

第二种完全参照二进制，可知N(自减一后)所落在的数字最近的次数填满数字，后来计算时很方便。

 void init(){

     P[]=;P[]=;

     nP[]=;nP[]=;

     for(int i=;i<=;++i){

         P[i]=*P[i-];

         nP[i]=P[i]-;

     }

 }

 ll getbound(ll& N){

     ll bound=;

     for(int i=;i>=;--i){

         if(N>=nP[i]){

             N-=nP[i];

             bound+=P[i-];

         }

     }

     return bound;

 }

计算时可以可利用每个数字出现的次数，是1(2^0)的倍数的出现过一次，是2(2^1)的倍数的额外出现过一次，是4(2^2)的倍数的又额外出现一次，，，(这也恰恰是后缀0的意义)

在这里贴两份按照上述两种方法写的代码。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll MOD=1e9+;

 ll P[];

 ll nP[];

 ll a[];

 ll arr[];

 ll lowbit(ll x){

     ll low=x&(-x);

     ll cnt=;

     while(low>>=){

         cnt++;

     }

     return cnt;

 }

 void init(){

     P[]=;P[]=;

     nP[]=;nP[]=;

     for(int i=;i<=;++i){

         P[i]=*P[i-];

         nP[i]=P[i]-;

     }

     //a[1]=1;a[2]=1;

     //arr[1]=1;arr[2]=2;

     //for(int i=3;i<101;i++){

     //    a[i]=a[i-a[i-1]]+a[i-1-a[i-2]];

     //    arr[i]=arr[i-1]+a[i];

     //}

     //for(int i=1;i<101;++i) printf("%lld\n",arr[i]);

 }

 ll inv(ll a,ll m){

     if(a==) return ;

     return inv(m%a,m)*(m-m/a)%m;

 }

 ll getbound(ll N){

     ll bound=;

     for(int i=;i>=;--i){

         while(N>=nP[i]){

             N-=nP[i];

             bound+=P[i-];

         }

     }

     return bound;

 }

 int main(){

     //freopen("data.in","r",stdin);

     //freopen("data1.out","w",stdout);

     init();

     int T;

     scanf("%d",&T);

     while(T--){

         ll N;

         scanf("%lld",&N);

         if(N==) puts("");

         else{

             ll ans=;

             N-=1ll;

             ll bound=;

             bound=getbound(N);

             //printf("bound = %lld\n",bound);

             ll cnt=lowbit(bound)+1ll;

             ll tot=N;

             for(ll i=;i<=cnt;++i){

                 if(bound==getbound(N+i)) tot++;

                 else break;

             }

             ll _m2=inv(,MOD);

             //printf("%lld\n",_m2);

             for(int i=;i<=;++i){

                 if(P[i]<=bound){

                     ll M=bound/P[i];

                     ans=(ans+(P[i]%MOD)*(M%MOD)%MOD*((M+1ll)%MOD)%MOD*_m2%MOD)%MOD;

                 }

                 else break;

             }

             //printf("1:%lld\n",(ans+1)%MOD);

             ans=(ans-(bound)*(tot-N)%MOD+MOD)%MOD;

             printf("%lld\n",(ans+1ll)%MOD);

             //printf("%I64d %I64d\n",(ans+1ll)%MOD,arr[N+1]);

             //最后加一

         }

     }

     return ;

 }

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll MOD=1e9+;

 ll P[];

 ll nP[];

 ll a[];

 ll arr[];

 ll lowbit(ll x){

     ll low=x&(-x);

     ll cnt=;

     while(low>>=){

         cnt++;

     }

     return cnt;

 }

 void init(){

     P[]=;P[]=;

     nP[]=;nP[]=;

     for(int i=;i<=;++i){

         P[i]=*P[i-];

         nP[i]=P[i]-;

     }

     //a[1]=1;a[2]=1;

     //arr[1]=1;arr[2]=2;

     //for(int i=3;i<101;i++){

     //    a[i]=a[i-a[i-1]]+a[i-1-a[i-2]];

     //    arr[i]=arr[i-1]+a[i];

     //}

     //for(int i=1;i<101;++i) printf("%lld\n",arr[i]);

 }

 ll inv(ll a,ll m){

     if(a==) return ;

     return inv(m%a,m)*(m-m/a)%m;

 }

 ll getbound(ll& N){

     ll bound=;

     for(int i=;i>=;--i){

         if(N>=nP[i]){

             N-=nP[i];

             bound+=P[i-];

         }

     }

     return bound;

 }

 int main(){

     //freopen("data.in","r",stdin);

     //freopen("data1.out","w",stdout);

     init();

     int T;

     scanf("%d",&T);

     while(T--){

         ll N;

         scanf("%lld",&N);

         if(N==) puts("");

         else{

             ll ans=;

             N-=1ll;

             ll bound=;

             bound=getbound(N);

             //printf("bound = %lld\n",bound);

             //ll cnt=lowbit(bound)+1ll;

             //ll tot=N;

             //for(ll i=1;i<=cnt;++i){

             //    if(bound==getbound(N+i)) tot++;

             //    else break;

             //}

             ll _m2=inv(,MOD);

             for(int i=;i<=;++i){

                 if(P[i]<=bound){

                     ll M=bound/P[i];

                     ans=(ans+(P[i]%MOD)*(M%MOD)%MOD*((M+1ll)%MOD)%MOD*_m2%MOD)%MOD;

                 }

                 else break;

             }

             //printf("1:%lld\n",(ans+1)%MOD);

             ans=(ans+(bound+)*N%MOD)%MOD;

             printf("%lld\n",(ans+1ll)%MOD);

             //printf("%I64d %I64d\n",(ans+1ll)%MOD,arr[N+1]);

             //最后加一

         }

     }

     return ;

 }

然后，比赛时WA了两发，其实规律找到了，但错在了计算，算总和时，第一个错误处是没用逆元，第二个错误处是P[i]在N为1e18时奇大，应该先mod在相乘。

血的教训。

Chiaki is interested in an infinite sequence a1,a2,a3,..., which is defined as follows:

an={1an−an−1+an−1−an−2n=1,2n≥3

Chiaki would like to know the sum of the first n terms of the sequence, i.e. ∑i=1nai. As this number may be very large, Chiaki is only interested in its remainder modulo (109+7).

巴特西

HDU 6304 Chiaki Sequence Revisited

最新文章

热门文章