竞赛讨论区 > 多校(第四场)C题 数位DP
头像
BiteTheDust
发布于 2018-07-29 16:15
+ 关注

多校(第四场)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;
}



全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐