牛客网暑期ACM多校训练营（第四场） C Chiaki Sequence Reloaded_综合

题目链接: 点此

题意:

很简单的题意,就是求那个式子的前 $n$ 项和

做法:

看的大佬博客，没看懂题解

这个式子,可以看出来 $a(n)=a({\frac{n}{2}})+(-1)^{\frac{n(n+1)}{2}}$
$(-1)^{\frac{n(n+1)}{2}}$ 这个可以看出来 $n\%4=1 或 n\%4=2$ 时等于 -1 ,其他等于 1,以二进制来看就是末尾相同的是1不同的是-1
在展开一下
$a(n)=a({\frac{n}{4}})+(-1)^{\frac{\frac{n}{2}(\frac{n}{2}+1)}{2}}+(-1)^{\frac{n(n+1)}{2}}$
一直展开可得(设 $S(n)=(-1)^{\frac{n(n+1)}{2}}$ )
$a(n)=S(n)+S(n>>1)+S(n>>2)+S(n>>3)+S(n>> \dots )+a(1)$
$a(1)$ 是0<script type="math/tex" id="MathJax-Element-1395">0</script>,可以忽略,这也就是题解说的

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define rd(a) scanf("%d",&a)
#define rld(a) scanf("%lld",&a)
#define rs(a) scanf("%s",a)
#define me(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
const ll maxn=3e5+10;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const double PI=acos(-1);
int d[64];
int dp[64][3][200];
ll dfs(ll pos,ll now,ll limit,ll num){if(pos==-1){return abs(64-num);}if(!limit&&dp[pos][now][num]!=-1) return dp[pos][now][num];int len=limit?d[pos]:1;ll ans=0;for(int i=0;i<=len;i++){if(now==2&&i==0) ans+=dfs(pos-1,2,limit&(i==len),num);else if(now==2&&i==1) ans+=dfs(pos-1,1,limit&(i==len),num);else ans+=dfs(pos-1,i,limit&(i==len),num+((now^i)?-1:1));ans%=mod;}if(!limit) dp[pos][now][num]=ans;return ans;
}void slove(ll x){int len=0;while(x){d[len++]=x&1;x>>=1;}printf("%lld\n",dfs(len-1,2,1,64));}
int main(){int t;rd(t);me(dp,-1);while(t--){me(d,0);ll n;rld(n);slove(n);}return 0;
}