【数位DP】[LOJ10163]Amount of Degrees

发现自己以前对数位DP其实一窍不通...

这题可以做一个很简单的转换：一个数如果在$b$进制下是一个01串，且1的个数恰好有k个，那么这个数就是合法的（刚开始没判断必定是01串，只判断了1的个数竟然有60pts，数据可真的水~）

这个结论显然成立，也不需要什么证明啦qaq~

然后数位DP就好了

转化为b进制后要么插1要么插0，$dp[x][cnt]$表示当前处理到第i为，已经有cnt个1的情况下

转移方程：

$$dp[x][cnt]=\sum dp[x-1][cnt+1](当前位为1)$$

$$dp[x][cnt]=\sum dp[x-1][cnt](当前位为0)$$

记忆化搜索就好了

 #include<bits/stdc++.h>

 #define writeln(x)  write(x),puts("")

 #define writep(x)   write(x),putchar(' ')

 using namespace std;

 inline int read(){

     int ans=,f=;char chr=getchar();

     while(!isdigit(chr)){if(chr=='-') f=-;chr=getchar();}

     while(isdigit(chr)){ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

     return ans*f;

 }void write(int x){

     if(x<) putchar('-'),x=-x;

     if(x>) write(x/);

     putchar(x%+'');

 }const int M = ;

 int dp[M][M],a[M],tp,l,r,x,y,k,b;

 int dfs(int x,int cnt,int lim){

     if(cnt>k)return ;

     if(x==)return cnt==k;

     if(!lim&&dp[x][cnt]!=-)return dp[x][cnt];

     int ans=,up=b-;

     if(lim)up=a[x];

     for(int i=;i<=up;i++){

         if(i==)ans+=dfs(x-,cnt+,lim&&(a[x]==i));

         else if(!i)ans+=dfs(x-,cnt,lim&&(a[x]==i));

     }

     if(!lim)dp[x][cnt]=ans;

     return ans;

 }

 inline int Solve(int x){

     int tp=;

     while(x){a[++tp]=x%b;x/=b;}

     return dfs(tp,,);

 }

 int main(){

     memset(dp,-,sizeof(dp));

     l=read(),r=read(),k=read(),b=read();

     l=Solve(l-);r=Solve(r);

     writeln(r-l);

     return ;

 }

巴特西

【数位DP】[LOJ10163]Amount of Degrees

最新文章

热门文章