我看了半天的數位 DP，DP 沒學會，人倒是麻了。
一般用於求解給你一個區間 \([l,r]\)，問你其中滿足條件的數有多少個。
這種題目還是蠻常見的，我們一般情況下暴力只能拿一少部分分，之前我看著那個 \(n\le 10^{18}\) 是一臉懵逼，這東西 \(O(n)\) 都過不去，啥高階的東西能 A 啊。
然後就有了今天讓我麻了的數位 DP。
題目中給的讓我們難以下手，我們不如轉化一下：求 \([1,r]\) 中符合限制的數並減去 \([1,l-1]\) 的數。
這樣就好處理多了，當然也可以從 \(0\) 開始，根據題目而定。
然後我們把要求的 \([1,x]\) 區間中的 \(x\) 給一位一位分解開，然後 dfs 往裡面填數。
在分解的時候，我們用一個陣列 \(a[i]\) 來儲存從高位到低位（一般是）的數位，來當作填數的限制。
我們在 dfs 的時候，傳的引數至少是包含 pos 當前填到第幾個數以及 limit 也就是當前點是否有限制，如果有的話，我們在後面遍歷當前點填的數的時候直接呼叫之前的 \(a[]\) 陣列就好了。
當然我們在 dfs 的時候是要記憶化的，不然複雜度直接飆升，我們可以根據題目給的限制條件來把狀態相同的歸到一類然後存放到陣列裡面，然後我們就可以在遇到與當前狀態相同的時候直接呼叫記憶化陣列來讓我們的複雜度變得美麗。
遍歷每一個數的時候一般分為兩種情況，一個有前導零，一個沒有前導零。
code:
#include <bits/stdc++.h>
#define int long long
#define N 20
using namespace std;
int a[N], cnt, f[N][N << 3][2][2], dight;
inline int dfs(int p, int cntd, int lead, int limit)//p是當前位置，cntd是當前答案lead是有沒有前導零。limit是當前數位列舉到的數量上限
{
if(p == cnt) return cntd;//到了就直接返回搜到的值
if(f[p][cntd][lead][limit] != -1) return f[p][cntd][lead][limit];//記憶化，以前搜過了就直接返回
int ans = 0;//統計答案
for(int v = 0; v <= (limit ? a[p] : 9); v ++)//列舉當前點可以是哪些數位
{
if(lead && v == 0)//如果要是當前點有前導零，並且當前的點的下一個列舉的是0
ans += dfs(p + 1, cntd, 1, limit && v == a[p]);//答案累加，計算當前狀態下的答案標記有前導零
else
ans += dfs(p + 1, cntd + (v == dight), 0, limit && v == a[p]);//正常情況
}
return f[p][cntd][lead][limit] = ans;//返回答案的同時記憶化
}
inline int fx(int x)
{
cnt = 0;
memset(f, -1 , sizeof f);
memset(a, 0, sizeof a);//清空陣列
while(x) a[cnt ++] = x % 10, x /= 10;//由低位到高位
reverse(a, a + cnt);//反轉一下讓他順序變正常
return dfs(0, 0, 1, 1);//開始搜尋 前面有0並且第一個數是有限制的
}
signed main()
{
int L, R;
cin >> L >> R;
for(int i = 0; i <= 9; i ++)//列舉九個數位
{
dight = i;//更新dight的值
cout << fx(R) - fx(L - 1) << " ";//跑一遍輸出當前數位出現的次數
}
return 0;
}
和前面講的一樣，利用記憶化搜尋，註釋應該很清楚了吧。
數位 DP 板子題。
我們設 \(f_{i,j}\) 為當前從左往右列舉到第 \(i\) 個數沒有列舉時，當前列舉完的 \(1\) 的個數為 \(j\) 時的能得到的有 \(k\) 個 \(1\) 的個數。
我們用 ? 來表示當前點沒有填入，假設我們現在從左往右填，當前的狀態是 10101?????，我們 dfs 完以後，直接存入 \(f_{6,3}\) 裡，我們要是再列舉到類似 10011????? 這種的，我們可以發現，後面問號的可能性是一樣的，也就是說，他們得到的答案是一樣的，那麼我們就可以進行記憶化了。
我們對於給定的 \(n\) 按照其他的數位 DP 一樣拆成二進位制下的數，將每一位都存放到 \(a_{i}\) 裡，也就是說 \(a_{i}\) 表示從左往右第 \(i\) 個數可以填 \(1\sim a_{i}\)。
由於這裡的情況很少，只有 \(0\) 和 \(1\)，所以可以直接展開回圈。
code：
#include <bits/stdc++.h>
#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 << fx(n) << endl;
return 0;
}