動態(tài)規(guī)劃——數位DP
”某一區(qū)間“滿足某種性質
技巧1：[x,y]=f[y]-f[x-1];
技巧2：樹;
模板如下：
//框架模板數位dp
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int f[N][10]; //f[i][j]:長度為i，以j開頭的滿足條件的數的個數
void init()//解決實質方法 初始化f
{
}
int dp(int x)//解決區(qū)間問題
{
if(x==0)return 0;
vector<int> nums;
while(x)nums.push_back(x%10),x=x/10;
int res=0;
int last=0;//用來記錄前面有關系的一個性質
for(int i=nums.size()-1;i>=0;i--)
{
int x=nums[i];
//先處理左邊分支
//繼續(xù)討論處理右邊分支，條件判斷，更新last，最后i=0時候res更新
}
return res;
}
int main()
{
init();
cin>>a>>b;
cout<<dp(b)-dp(a-1)<<endl;
return 0;
}
例1：度的數量
分析：
#include<bits/stdc++.h>
using namespace std;
int x,y,k,b;
const int N=35;
int f[N][N];
void init()//組合數——楊輝三角形
{
for(int i=0;i<N;i++)
{
for(int j=0;j<=i;j++)
{
if(!j)f[i][j]=1;
else f[i][j]=f[i-1][j-1]+f[i-1][j];
}
}
}
int dp(int x)
{
if(!x)return 0;
vector<int> nums;
while(x)nums.push_back(x%b),x=x/b;
int res=0;
int last=0;//記錄前面的位數占用的1
for(int i=nums.size()-1;i>=0;i--)
{
int x=nums[i];
if(x)//為了防止超出區(qū)間只有x不為0才有選擇
{
res+=f[i][k-last];//如果當前位為0
if(x>1)//如果當前位選擇為1
{
res+=f[i][k-last-1];
break;
}
else//當前本來就為1，就需要繼續(xù)討論
{
last++;
if(last>k)break;
}
}
if(i==0&&last==k)res++;//最右側分支上的1
}
return res;
}
int main()
{
cin>>x>>y>>k>>b;
init();
cout<<dp(y)-dp(x-1)<<endl;
return 0;
}
例2、數字游戲
分析：
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int f[N][N];//f[i][j]為長度為i，且以j開頭的的有多少個不降數
void init()//動態(tài)規(guī)劃預處理
{
for(int i=0;i<=9;i++)f[1][i]=1;
for(int i=2;i<=N;i++)
{
for(int j=0;j<=9;j++)
{
for(int k=j;k<=9;k++)
{
f[i][j]+=f[i-1][k];
// cout<<f[i][j]<<endl;
}
}
}
}
int dp(int x)
{
if(x==0)return 1;
vector<int> nums;
while(x)nums.push_back(x%10),x=x/10;
int res=0;
int last=0;//用來記錄上一位數字
for(int i=nums.size()-1;i>=0;i--)
{
int y=nums[i];
for(int j=last;j<y;j++)//左邊分支的處理
{
res+=f[i+1][j];
}
if(y<last)break;
last=y;//右邊分支的處理
if(i==0)res++;//右邊最后分支的處理
}
return res;
}
int main()
{e
init();
while(cin>>ea>>b)
{
cout<<dp(b)-dp(a-1)<<endl;
}
return 0;
}
例3、 Windy數
如果要求dp（1567），由于第一個根節(jié)點的分叉左枝干是從1開始，那么就等于0-999都沒有算進res里面
好好理解f的含義，例如f[3] [9]表示最高位為9長度為3 滿足條件的windy數的個數，那么是9_ _,900–999中的個數
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int f[N][10];
void init()//解決實質方法
{
for(int i=0;i<=9;i++)f[1][i]=1;
for(int i=2;i<=N;i++)
{
for(int j=0;j<=9;j++)
{
for(int k=0;k<=9;k++)
{
if(abs(j-k)>=2)
f[i][j]+=f[i-1][k];
}
}
}
}
int dp(int x)//解決區(qū)間問題
{
if(x==0)return 0;
vector<int> nums;
while(x)nums.push_back(x%10),x=x/10;
int res=0;
int last=-2;//用來記錄前面有關系的一個性質
for(int i=nums.size()-1;i>=0;i--)
{
int y=nums[i];
for(int j=i==nums.size()-1;j<y;j++)
{
if(abs(j-last)>=2)
res+=f[i+1][j];
}
if(abs(y-last)>=2)last=y;
else break;
if(!i)res++;
}
//特殊處理000——的情況 ，也就是一開始少算了前導0的部分區(qū)間
for(int i=1;i<nums.size();i++)
{
for(int j=1;j<=9;j++)
res+=f[i][j];
}
return res;
}
int main()
{
init();
cin>>a>>b;
cout<<dp(b)-dp(a-1)<<endl;
return 0;
}
4、數字游戲
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int M;
int f[N][10][100]; //數長為i，以j為開頭，每個數字之和模為t
void init()//解決實質方法
{
memset(f,0,sizeof(f));
for(int i=0;i<=9;i++)f[1][i][i%M]++;
for(int i=2;i<N;i++)
{
for(int j=0;j<=9;j++)
{
for(int t=0;t<=M-1;t++)
{
for(int k=0;k<=9;k++)
{
f[i][j][t]+=f[i-1][k][((t-j)%M+M)%M];
// cout<<f[i][j][t]<<endl;
}
}
}
}
}
int dp(int x)//解決區(qū)間問題
{
if(x==0)return 1;
vector<int> nums;
while(x)nums.push_back(x%10),x=x/10;
int res=0;
int last=0;//用來記錄前面有關系的一個性質
for(int i=nums.size()-1;i>=0;i--)
{
int y=nums[i];
for(int j=0;j<y;j++)//處理左邊的分支
{
res+=f[i+1][j][(M+-last)%M];
}
last=(last+y)%M;
if(i==0&&last==0)res++;
}
return res;
}
int main()
{
while(cin>>a>>b>>M)
{
init();
cout<<dp(b)-dp(a-1)<<endl;
}
return 0;
}
5、 不要62
有些該有的條件不可省略
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=10;
int f[N][10]; //數長為i，以j為開頭
//f[i][j]+=f[i-1][k],如果j為2,k就不會為6
void init()//解決實質方法
{
for(int i=0;i<=9;i++)f[1][i]=1;
f[1][4]=0;
for(int i=2;i<=N;i++)
{
for(int j=0;j<=9;j++)
{
if(j==4)continue;
for(int k=0;k<=9;k++)
{
if(k==4||(j==6&&k==2))continue;
f[i][j]+=f[i-1][k];
}
}
}
}
int dp(int x)//解決區(qū)間問題
{
if(x==0)return 1;
vector<int> nums;
while(x)nums.push_back(x%10),x=x/10;
int res=0;
int last=0;//用來記錄前面有關系的一個性質
for(int i=nums.size()-1;i>=0;i--)
{
int y=nums[i];
for(int j=0;j<y;j++)
{
if(last==6&&j==2)continue;
res+=f[i+1][j];
}
if(last==6&&y==2)break;
if(y==4)break;
last=y;
if(!i)res++;
}
return res;
}
int main()
{
init();
while(~scanf("%d %d",&a,&b),a&&b)
{
cout<<dp(b)-dp(a-1)<<endl;
}
return 0;
}
6、
[USACO06NOV] Round Numbers S
如果一個正整數的二進制表示中， 0 0 0 的數目不小于 1 1 1 的數目，那么它就被稱為「圓數」。
例如， 9 9 9 的二進制表示為 1001 1001 1001，其中有 2 2 2 個 0 0 0 與 2 2 2 個 1 1 1。因此， 9 9 9 是一個「圓數」。
請你計算，區(qū)間 [ l , r ] [l,r] [l,r] 中有多少個「圓數」。
一行，兩個整數 l , r l,r l,r。
一行，一個整數，表示區(qū)間 [ l , r ] [l,r] [l,r] 中「圓數」的個數。
2 12
6
【數據范圍】
對于 100 % 100\% 100% 的數據， 1 ≤ l , r ≤ 2 × 1 0 9 1\le l,r\le 2\times 10^9 1≤l,r≤2×109。
【樣例說明】
區(qū)間 [ 2 , 12 ] [2,12] [2,12] 中共有 6 6 6 個「圓數」，分別為 2 , 4 , 8 , 9 , 10 , 12 2,4,8,9,10,12 2,4,8,9,10,12。
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=50;
int f[N][2][N];//數長為i,圓數的個數
//f[i][0][j]+=f[i][0][j-1]
//f[i][j][p][t]=f[i-1][k1][p-j][t-t*i0]
//第三維為數字之和的模，第四維為證書之和的模
void init()//解決實質方法
{
f[1][0][1]=1;
f[1][1][0]=1;
for(int i=2;i<N;i++)
{
for(int j=0;j<=1;j++)
{
for(int k=i;k>=0;k--)//表示的是0的個數
{
if(j)f[i][j][k]=f[i-1][0][k]+f[i-1][1][k];
if(k&&!j) f[i][j][k]=f[i-1][0][k-1]+f[i-1][1][k-1];
}
}
}
}
int dp(int x)//解決區(qū)間問題
{
// if(x==0)return 1;
vector<int> nums;
while(x)nums.push_back(x%2),x=x/2;
int res=0;
int last=0;//用來記錄前面有關系的一個性質
int l=nums.size();
for(int i=nums.size()-2;i>=0;i--)
{
int y=nums[i];
if(y)//y為1———
{
for(int j=l-last;j>=(l+1)/2-last;j--)
{
if(j<=i+1)res+=f[i+1][0][j];
}
}
if(!y)last++;
if(!i&&last>=(l+1)/2)res++;
}
for(int i=1;i<l;i++){
for(int j=i;j>=(i+1)/2;j--)
res+=f[i][1][j];
}
return res;
}
int main()
{
init();
cin>>a>>b;
cout<<dp(b)-dp(a-1)<<endl;
return 0;
}
7、花神花神的數論題
眾所周知，花神多年來憑借無邊的神力狂虐各大 OJ、OI、CF、TC …… 當然也包括 CH 啦。
話說花神這天又來講課了。課后照例有超級難的神題啦…… 我等蒟蒻又遭殃了。 花神的題目是這樣的：設 sum ( i ) \text{sum}(i) sum(i) 表示 i i i 的二進制表示中 1 1 1 的個數。給出一個正整數 N N N ，花神要問你 ∏ i = 1 N sum ( i ) \prod_{i=1}^{N}\text{sum}(i) ∏i=1N?sum(i) ，也就是 sum ( 1 ) ～ sum ( N ) \text{sum}(1)\sim\text{sum}(N) sum(1)～sum(N) 的乘積。
一個正整數 N N N。
一個數，答案模 10000007 10000007 10000007 的值。
3
2
對于 100 % 100\% 100% 的數據， 1 ≤ N ≤ 1 0 15 1\le N\le 10^{15} 1≤N≤1015。文章來源：http://www.zghlxwxcb.cn/news/detail-762144.html
運用快速冪的方法文章來源地址http://www.zghlxwxcb.cn/news/detail-762144.html
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll x;
const ll N=55;
ll f[N][2][N];//長度為i，以j開頭的，1的個數為k的數有多少個
ll mod=10000007;
void init()//解決實質方法
{
f[1][0][0]=1;
f[1][1][1]=1;
for(int i=2;i<N;i++)
{
for(int j=0;j<=1;j++)
{
for(int k=i;k>=0;k--)//表示的是1的個數
{
if(j&&k)f[i][j][k]=f[i-1][0][k-1]+f[i-1][1][k-1];
if(!j) f[i][j][k]=f[i-1][0][k]+f[i-1][1][k];
}
}
}
}
ll quick_mi(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
b=b/2;
a=a*a%mod;
}
return res;
}
ll dp(ll x)//解決區(qū)間問題
{
// if(x==0)return 1;
vector<int> nums;
while(x)nums.push_back(x%2),x=x/2;
ll res=1;
int last=1;//用來記錄前面有關系的一個性質
int l=nums.size();
for(int i=nums.size()-2;i>=0;i--)//從第二位分支開始
{
int y=nums[i];
if(y)//y為1———
{
for(int j=0;j<=i;j++)
{
res=(res*quick_mi(j+last,f[i+1][0][j])%mod)%mod;
}
}
if(y)last++;//增加1的個數
if(!i)res=(res*last)%mod;
}
for(int i=1;i<l;i++){
for(int j=1;j<=i;j++)
res=(res*quick_mi(j,f[i][1][j])%mod)%mod;
}
return res;
}
int main()
{
init();
cin>>x;
cout<<dp(x)<<endl;
return 0;
}
到了這里，關于動態(tài)規(guī)劃——數位的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
![[ACM學習] 動態(tài)規(guī)劃基礎之一二三維dp](https://imgs.yssmx.com/Uploads/2024/02/791232-1.png)
