【数位DP】[LOJ10163]Amount of Degrees

古城微笑少年丶 2023-06-01 06:10 21阅读 0赞

发现自己以前对数位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)$$

记忆化搜索就好了

1 #include<bits/stdc++.h>
     2 #define writeln(x)  write(x),puts("")
     3 #define writep(x)   write(x),putchar(' ')
     4 using namespace std;
     5 inline int read(){
     6     int ans=0,f=1;char chr=getchar();
     7     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     8     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
     9     return ans*f;
    10 }void write(int x){
    11     if(x<0) putchar('-'),x=-x;
    12     if(x>9) write(x/10);
    13     putchar(x%10+'0');
    14 }const int M = 50;
    15 int dp[M][M],a[M],tp,l,r,x,y,k,b;
    16 int dfs(int x,int cnt,int lim){
    17     if(cnt>k)return 0;
    18     if(x==0)return cnt==k;
    19     if(!lim&&dp[x][cnt]!=-1)return dp[x][cnt];
    20     int ans=0,up=b-1;
    21     if(lim)up=a[x];
    22     for(int i=0;i<=up;i++){
    23         if(i==1)ans+=dfs(x-1,cnt+1,lim&&(a[x]==i));
    24         else if(!i)ans+=dfs(x-1,cnt,lim&&(a[x]==i));
    25     }
    26     if(!lim)dp[x][cnt]=ans;
    27     return ans;
    28 }
    29 inline int Solve(int x){
    30     int tp=0;
    31     while(x){a[++tp]=x%b;x/=b;}
    32     return dfs(tp,0,1);
    33 }
    34 int main(){
    35     memset(dp,-1,sizeof(dp));
    36     l=read(),r=read(),k=read(),b=read();
    37     l=Solve(l-1);r=Solve(r);
    38     writeln(r-l);
    39     return 0;
    40 }

转载于:https://www.cnblogs.com/zhenglw/p/11575301.html