我看了半天的数位 DP，DP 没学会，人倒是麻了。
解决什么
一般用于求解给你一个区间 ([l,r])，问你其中满足条件的数有多少个。
这种题目还是蛮常见的，我们一般情况下暴力只能拿一少部分分，之前我看着那个 (nle 10^{18}) 是一脸懵逼，这东西 (O(n)) 都过不去，啥高级的东西能 A 啊。
然后就有了今天让我麻了的数位 DP。
思想
题目中给的让我们难以下手，我们不如转化一下：求 ([1,r]) 中符合限制的数并减去 ([1,l-1]) 的数。
这样就好处理多了，当然也可以从 (0) 开始，根据题目而定。
然后我们把要求的 ([1,x]) 区间中的 (x) 给一位一位分解开，然后 dfs 往里面填数。
在分解的时候，我们用一个数组 (a[i]) 来存储从高位到低位（一般是）的数字，来当作填数的限制。
我们在 dfs 的时候，传的参数至少是包含 pos 当前填到第几个数以及 limit 也就是当前点是否有限制，如果有的话，我们在后面遍历当前点填的数的时候直接调用之前的 (a[]) 数组就好了。
当然我们在 dfs 的时候是要记忆化的，不然复杂度直接飙升，我们可以根据题目给的限制条件来把状态相同的归到一类然后存放到数组里面，然后我们就可以在遇到与当前状态相同的时候直接调用记忆化数组来让我们的复杂度变得美丽。
遍历每一个数的时候一般分为两种情况，一个有前导零，一个没有前导零。
P2602 [ZJOI2010] 数字计数
code:
#include
#define int long long
#define N 20
using namespace std;
int a[N], cnt, f[N][N > L >> R;
for(int i = 0; i 和前面讲的一样，利用记忆化搜索，注释应该很清楚了吧。
P8764 [蓝桥杯 2021 国 BC] 二进制问题
数位 DP 板子题。
我们设 (f_{i,j}) 为当前从左往右枚举到第 (i) 个数没有枚举时，当前枚举完的 (1) 的个数为 (j) 时的能得到的有 (k) 个 (1) 的个数。
我们用 ? 来表示当前点没有填入，假设我们现在从左往右填，当前的状态是 10101?????，我们 dfs 完以后，直接存入 (f_{6,3}) 里，我们要是再枚举到类似 10011????? 这种的，我们可以发现，后面问号的可能性是一样的，也就是说，他们得到的答案是一样的，那么我们就可以进行记忆化了。
我们对于给定的 (n) 按照其他的数位 DP 一样拆成二进制下的数，将每一位都存放到 (a_{i}) 里，也就是说 (a_{i}) 表示从左往右第 (i) 个数可以填 (1sim a_{i})。
由于这里的情况很少，只有 (0) 和 (1)，所以可以直接展开循环。
code：
#include
#define int long long
#define N 100
using namespace std;
int n, k, a[N], f[N][N];//枚举到第i个数当前当前j个1的个数
inline int dfs(int p, int limit, int cnt)
{
if( cnt > k ) return 0;
if(! p) return (cnt == k ? 1 : 0);
if(! limit && f[p][cnt] != -1) return f[p][cnt];
int res = 0, flag = (limit ? a[p] : 1);
res += dfs(p - 1, limit && flag == 0, cnt);
if(flag) res += dfs(p - 1, limit && flag == 1, cnt + 1);
if (! limit) f[p][cnt] = res;
return res;
}
inline int fx(int x)
{
memset(f, -1, sizeof f);
int len = 0;
while(x) a[++ len] = (x & 1), x >>= 1;
return dfs(len, 1, 0);
}
signed main()
{
cin >> n >> k;
cout 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
我们努力为自己的产品所遇到的问题思考解决办法，但在这篇文章中我将给大家分享几种常用的技术，包括分离锁、并行数据结构、保护数据而非代码、缩小锁的作用范围，这几种技术可以使我们不使用任何工具来检测死锁。 锁不是问题的根源，锁之间的竞争才是 通常在多线程的代码中遇到…
