大致题意： 让你求出一段区间内与\(7\)无关的数的平方和。与\(7\)无关的数指整数中任意一位不为\(7\)、整数的每一位加起来的和不是\(7\)的整数倍、这个整数不是\(7\)的倍数。
数位\(DP\)
这题应该比较显然是一道 题。
如何记录状态
这道题关键就在于如何记录状态，其余的就和普通的数位\(DP\)差不多了。
我们可以用\(f_{x,s1,s2}\)来表示还剩\(x\)位，这个数除末\(x\)位以外模\(7\)余\(s1\)，这个数每一位之和除末\(x\)位以外模\(7\)余\(s2\)时所有与\(7\)无关的数的末\(x\)位的平方和。
但是，如果光光记录平方和，转移就有点困难了。
所以，我们先要来一点恶心的数学转化。
数学转化
让我们来研究一下\((x_1+t*10^y)^2+(x_2+t*10^y)^2+...+(x_n+t*10^y)^2\)这个式子。
先由完全平方公式可得：
\[原式=(x_1^2+2*x_1*t*10^y+10^{2y})+(x_2^2+2*x_2*t*10^y+10^{2y})+...+(x_n^2+2*x_n*t*10^y+10^{2y})\]
然后，我们将其去括号并重新组合，可得：
\[原式=(x_1^2+x_2^2+...+x_n^2)+2*t*10^y*(x_1+x_2+...+x_n)+(t*10^y)^2*n\]
如果用\(f(n)\)来表示\(x_1+x_2+...+x_n\)，\(f^2(n)\)来表示\(x_1^2+x_2^2+...+x_n^2\)，则：
\[原式=f^2(n)+2*t*10^y*f(n)+(t*10^y)^2*n\]
我们可以预处理出\(10^y\)，并对于每个状态记录下\(n,f(n)\)和\(f^2(n)\)，这样就可以实现\(O(1)\)转移了。
状态转移方程
用\(ns1\)来表示\((s1*10+i)\)%\(y\)，\(ns2\)来表示\((s2+i)\)%\(y\)。
\[n_{x,s1,s2}=\sum_{i=0}^{lim}n_{x-1,ns1,ns2}\]
\[f_{x,s1,s2}=\sum_{i=0}^{lim}f_{x-1,ns1,ns2}+n_{x-1,ns1,ns2}*i*10^{x-1}\]
\[f^2_{x,s1,s2}=\sum_{i=0}^{lim}f^2_{x-1,ns1,ns2}+2*i*10^x*f_{x-1,ns1,ns2}+(i*10^{x-1})^2*n_{x-1,ns1,ns2}\]
代码
#include#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define uint unsigned int#define LL long long#define ull unsigned long long#define swap(x,y) (x^=y,y^=x,x^=y)#define abs(x) ((x)<0?-(x):(x))#define INF 1e9#define Inc(x,y) ((x+=y)>=MOD&&(x-=MOD))#define MOD 1000000007using namespace std;LL n,m;class FIO{ private: #define Fsize 100000 #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++) #define pc(ch) (FoutSize