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

时间:2022-05-22 12:24:41

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

#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 ;
}