HDU 4507 吉哥系列故事——恨7不成妻

需要推下平方和的式子。。维护个数，和，平方和。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mod 1000000007LL

using namespace std;

long long bit[],tab[],ret=,t,l,r;

struct pnt

{

    long long val1,val2,val3;

    pnt (long long val1,long long val2,long long val3):val1(val1),val2(val2),val3(val3) {}

    pnt () {}

}dp[][][];

void get_bit(long long x)

{

    ret=;

    while (x) {bit[++ret]=x%;x/=;}

}

void get_table()

{

    tab[]=;

    for (long long i=;i<=;i++) tab[i]=tab[i-]*%mod;

    for (long long i=;i<=;i++)

        for (long long j=;j<=;j++)

            for (long long k=;k<=;k++)

            {

                dp[i][j][k].val1=dp[i][j][k].val2=dp[i][j][k].val3=-;

            }

    return;

}

pnt comb(pnt x,pnt y,long long pos,long long num)

{

    long long r1=,r2=,r3=;

    r1=((y.val3*tab[*(pos-)]%mod*num%mod*num%mod+(*(y.val2*tab[pos-]%mod)%mod*num)%mod)%mod+y.val1)%mod;

    r2=(y.val3*num%mod*tab[pos-]%mod+y.val2)%mod;

    r3=y.val3;

    x.val1=(x.val1+r1)%mod;

    x.val2=(x.val2+r2)%mod;

    x.val3=(x.val3+r3)%mod;

    return x;

}

pnt dfs(long long pos,long long val1,long long val2,bool flag)

{

    if (!pos)

    {

        if (val1 && val2) return pnt(,,);

        else return pnt(,,);

    }

    if ((!flag) && (~dp[pos][val1][val2].val1)) return dp[pos][val1][val2];

    pnt ans=pnt(,,);long long up=flag?bit[pos]:;

    for (long long i=;i<=up;i++)

    {

        if (i==) continue;

        ans=comb(ans,dfs(pos-,(val1*+i)%,(val2+i)%,flag&&i==up),pos,i);

    }

    if (!flag) dp[pos][val1][val2]=ans;

    return ans;

}

long long work(long long x)

{

    get_bit(x);

    return dfs(ret,,,).val1;

}

int main()

{

    scanf("%I64d",&t);get_table();

    for (long long i=;i<=t;i++)

    {

        scanf("%I64d%I64d",&l,&r);

        printf("%I64d\n",(work(r)-work(l-)+mod)%mod);

    }

    return ;

}