题目背景
SOURCE：NOIP2015-GDZSJNZX（难） 题目描述 Mike 正在在忙碌地发着各种各样的的短信。旁边的同学 Tom 注意到，Mike 发出短信的接收方手机号码似乎都满足着特别的性质，难道Mike 的好朋友是满足正态分布的？Tom 很好奇。 由于 Mike 有着自己最喜欢的数字 a ，并且 a 的范围是：2≤a≤9 。Tom 从这里入手，发现了一些端倪，假设 Mike 发的电话号码是一个十进制数字 S ，Tom 发现 S 会满足以下三个性质中的一个： 1．S 是 a 的倍数。 2．S 在十进制表示下的各项数字加起来是 a 的倍数。 3．S 的某一位是 a 。 比如说当 a=7 时，21，16，17 这三个数字组成的电话号码都是会被Mike发短信的，他们分别满足 1，2，3 性质。 Tom 在想：如果给你两个自然数 L，R，以及 Mike 最喜欢的数字 a ，在 [L,R] 中有多少个号码是 Mike 要发短信的手机号码，只需要你告诉他这些数字的平方和。比如说 3，7 是合法的，那么你应该输出 32 + 72 = 58 这个数。 当然，由于答案可能很大，你只需要将答案对 10^9 + 7 取模即可。 输入格式 输入的第一行包括一个正整数 T ，表示总共有 T 组询问。 接下来有 T 行，每行三个整数 L，R，A 。 输出格式 输出包括 T 行，每行一个整数，表示对 10^9 + 7 取模的答案。 样例数据 1 输入 3 2 20 6 3 203 7 11 771 2 输出 1884 1593269 32817226 备注 【数据范围】 对于 15% 的数据，0≤L≤R≤10^6，T=1 对于 35% 的数据，0≤L≤R≤10^7，T=1 另外有 25% 的数据，A=2；L=10k；R=10v；k和v都是自然数。 对于 100% 的数据，0≤L≤R≤10^18；2≤A≤9；T≤100先看一眼题面，再看一眼数据范围不难想到这题想考数位dp
但常规的数位dp只要求求出满足条件的数的个数，该题要求的是这些数的平方和，为了解决这个问题，我们可以先考虑这个问题的弱化版本：如何求出这些数的和？ 我们可以将普通数位dp要求的数的数量抽象成0维上的问题，那么该题就是要求二维问题，显然我们可以用0维的状态推出1维的状态，那么自然我们也可以用0维和1维的状态来推出二维的状态。那么我们可以利用完全平方式来推出答案，设前几位的值为a，当前位的值为b，那么，合并起来的值是（10a+b），那么合并起来的值的平方为100a2+20ab+b2，由于a和b都知道，那么就做完了。 注：状态转移方程有点恶心、 代码：#include#define ll long long#define mod 1000000007using namespace std;ll t,m,l,r,dp[3][20][10][10][2][2],num[20];// ^ 每一位的和 数的大小 是否出现过 是否满位 inline ll sol(ll x){ if(x==-1||x==0)return 0; ll ans=0,len=0; while(x)num[++len]=x%10,x/=10; for(int i=1;i<=(len>>1);++i)swap(num[i],num[len-i+1]); memset(dp,0,sizeof(dp)); for(int i=0;i