多校（第四场）C题 数位DP
题目大意是给出一个式子an 求其前n项的和。
首先我们可以发现 在n mod4 为0、3时 an=a[n/2]+1,n mod4为1、2时an=a[n/2]-1。
而从a1到an要经过log2 an次这样的加减，可以转化成二进制位上的问题。
把n化为二进制数组b,当某位bi与bi-1组成的二进制为0、3时+1，为1、2时-1，例如bi==1,bi-1==0，二进制就是10，十进制为2，此时-1。
此时我们就可以在log复杂度内求出an。
然后我们再利用数位dp,来求出前n项的和。
dp存储的第一维len表示位数。
第二维 if pre==2表示bi前一项为空，故不计算bi+1与bi，else pre表示前一位的值。
第三维为sum，表示前面位数累计的和，因为会有负值，故加上64最后再减去并取绝对值。
另外，因为对于+1时的0、3二进制分别为00，11，故我们可以通过bi+1==bi来判断加减。
以下为数位dp的代码。
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long i,n,m,dp[64][3][128],a[64],T;
long long dfs(int len,bool maxi,int pre,int sum)
{
if(dp[len][pre][sum]!=-1&&maxi==0)return dp[len][pre][sum];
long long cnt=0;
if(!len)return abs(sum-64);
int maxn=maxi?a[len]:1;
for(int i=0;i<=maxn;i++)
{
if(pre==2)
{
if(i)cnt+=dfs(len-1,maxi&&i==a[len],i,sum);
else cnt+=dfs(len-1,maxi&&i==a[len],pre,sum);
}
else
{
if(i==pre)cnt+=dfs(len-1,maxi&&i==a[len],i,sum+1);
else cnt+=dfs(len-1,maxi&&i==a[len],i,sum-1);
}
}
cnt%=mod;
return maxi?cnt:dp[len][pre][sum]=cnt;
}
long long div(long long tmp)
{
int p=0;
while(tmp)a[++p]=tmp%2,tmp/=2;
return dfs(p,1,2,64);
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
printf("%lld\n",div(n));
}
return 0;
}
