数位dp一直是个人弱项，惦记很久了，最近补了补，感受还行。ubuntu
解决一个区间中，知足某些条件（与每一位有关）的数的数量（或者带权的和）。spa
作法：考虑求前缀 \([1,x]\) 的答案。code
若是你是新手，请先考虑一下大概要怎么作，再继续看字符串
先把位（不必定是十进制）拆开来，而后是一个形如 "dp到第 \(i\) 位，..." 的 dp，通常能够用记忆化搜索，一位一位的填，使得它看起来友好一些（我的感受这样可读性好）。get
而后要解决 \(\le x\) 的限制。每次按照这样的规则来填数字：it
这个很好理解。好比说如今钦点下来是 \(123***\)，\(x=123456\)，那后面显然不能超过 \(456\)。入门
而若是如今钦点下来是 \(122***\)，那它就算是 \(122999\)，也不会超过 \(x\)。ast
用一个 lim 标记维护当前是否卡到上界。注意它应该被记在 dp 状态里。class
求区间知足：任意相邻两位的差都不超过 \(2\) 的数，的数量。扩展
dp 状态：到第几位，当前选了什么（以决定下一个可不能够选），lim
而后每次 dfs 扩展的时候，判断一下下一个填的是否合法，再加个记忆化，就好了。
求区间知足：将数当作字符串，没有任何长度 \(\ge 2\) 的回文串的数，的数量。
没有任何长度 \(\ge 2\) 回文串 \(\rightarrow\) 任意一个字符和它前面一个，两个都不一样。
这样就保证了没有长度等于 \(2,3\) 的回文串，而后其他的回文串都是由这两种扩展出来的，天然也没有了。
剩下就很好 dp 了，和上一个差很少。
hdu的题，我第一次学数位dp的时候被老师称做“毕业题”
你要能把这个题写出来，你数位dp就差很少了
当时看着老师标程打的，如今简单复习了一下，发现还挺好想的 而后把它秒了，其实就是一个傻逼缝合怪题
要知足三个条件：
区间求知足条件平方和。
这里涉及到一个带权求和。带权求和状态要变一下，表示从这位开始截取，的带权和。
好比说 \(x=123\)，填好了 \(11*\)，知足条件的数有 \(111\)，\(113\)，\(114\)，\(116\)，\(118\)
带权和为 \(1^2+3^2+4^2+6^2+8^2=126\)
为何要作一步截取呢？由于要方便转移。考虑转移，至关于，我先肯定好后面若干位，在它们的前面都填上相同的数字（这里至关于放上了 \(1\)）
而后填相同的数字能够看作是加法 （这里至关于 \(+10\)）
而后平方和，总体加，好作吧：再维护数量和一次方和，设为 dp[...][0/1/2]，对应数量，和，平方和
设如今总体加的为 \(a\)，后面一位的 dp[...][0/1/2] 记下来为 nex[0/1/2]，如今的是 cur[0/1/2]，则有：
cur[0]+=nex[0]; cur[1]+=nex[1]+nex[0]*a; cur[2]+=nex[2]+2*nex[1]*a+nex[0]*a*a
（就是拆括号搞一下就行）
对于条件：
求 \(\sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{m-1} \max(i\oplus j-k,0)\)
\(n,m,k\le 10^{18}\)
后面等价成 \(>k\) 的和，减去 \(>k\) 的数量乘以 \(k\)
拆成二进制，作数位 \(dp\)。记下三个 lim，表示是否卡在 \(n\) 的上界，\(m\) 的上界，\(k\) 的下界 （由于 \(k\) 那边是个 \(>\) 的限制）
而后上一题相似的求一下带权和就好了，要维护一下数量和总和。
因为数位 dp 的基本模型只有一个 log，因此能够带不少别的
题意：求区间能整除数位和的数的数量
好比 \(12\) 就知足条件由于 \(1+2\) 是 \(12\) 的倍数
\(x\le 10^{18}\)
注意到数位和不会超过 \(9\times 18=162\)
先枚举数位和 \(k\)，而后 dp 里设两维，一维表示当前数位和，一维表示当前数模 \(k\) 的余数。最后取答案就是 \(\%k=0\)，数位和 \(=k\) 的那个状态
复杂度是 \((9\times \log n^3)\log n\)，很是暴力