题目链接：http://acm.hdu.edu.cn/showPRoblem.php?pid=4507 题意：求[L,R](1 <= L <= R <= 10^18)区间内和7无关的数字的平方和。 如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍； 想法：如果不是求平方和，而是求个数的话，很容易写。重点就是如何求平方和：开一个三维dp[i][j][k]结构体，i表示第i位，j表示到从最高位到第i位的每一位的累加和模7，k表示最高位到第i位的数值模7，结构体由和7有关的数的个数（cnt），和7有关的数的和（sum），和7有关的数的平方和（squ_sum）组成。cnt很容易求，若求出cnt的话，在这个过程中加上i*a[pos]*cnt，sum也求出来了。对于求平方和因为(a+b)^2=a^2+b^2+2*a*b，所以squ_sum=squ_sum(后面的)+(i*b[pos]*cnt)^2+2*sum*i*b[pos]*cnt;(b[pos]相当于10^pos) 代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<queue>#include<cmath>#include<vector>#include<map>#include<stack>#include<iostream>#include<algorithm>using namespace std;#define ll long long#define bug() puts("wtf???")#define inf 0x3f3f3f3f#define scanfprint() freopen("1input.txt","r",stdin)#define printfprint() freopen("output.txt","w",stdout)#define mem(a,b) memset(a,b,sizeof(a))const int spot=1000+10;const int edge=100000+10;const int maxn=100000+10;const double pi=acos(-1.0);const ll l_mod=1e9+7;const double ips=0.000001;struct stu{ ll cnt,sum,squ_sum;} dp[25][10][10];ll a[25],b[25];void init() { int i; b[1]=1; for(i=2; i<=19; i++) b[i]=b[i-1]*10%l_mod; memset(dp,-1,sizeof(dp));}stu dfs(int pos,int sum,int mod,int last){ if(!pos) { stu temp={0}; temp.cnt=sum&&mod; temp.sum=temp.squ_sum=0; return temp; } if(!last&&dp[pos][sum][mod].cnt!=-1) return dp[pos][sum][mod]; stu temp={0},ans={0}; int num=last?a[pos]:9,i; for(i=0; i<=num; i++) { if(i==7) continue; temp=dfs(pos-1,(sum+i)%7,(mod*10+i)%7,i==num&&last); ans.cnt=ans.cnt+temp.cnt; ans.cnt%=l_mod; ans.sum+=(temp.cnt*i%l_mod*b[pos]%l_mod+temp.sum)%l_mod; ans.sum%=l_mod; ans.squ_sum+=(temp.squ_sum + 2*b[pos]*i%l_mod*temp.sum)%l_mod; ans.squ_sum%=l_mod; ans.squ_sum+=( temp.cnt*b[pos]%l_mod*b[pos]%l_mod*i*i%l_mod); ans.squ_sum%=l_mod; } if(!last) dp[pos][sum][mod]=ans; return ans;}ll cal(ll n){ int sizes=0; while(n) a[++sizes]=n%10,n/=10; stu ans=dfs(sizes,0,0,1); return ans.squ_sum;}int main(){ int nn; init(); scanf("%d",&nn); while(nn--) { ll l,r; cin>>l>>r; ll ans=cal(r)-cal(l-1); ans=(ans%l_mod+l_mod)%l_mod; cout<<ans<<endl; } return 0;}新闻热点
疑难解答
