首页 > 其他分享 >数位dp二则

数位dp二则

时间:2022-11-07 15:46:31浏览次数:69  
标签:数位 pre ll pos 二则 sum dp define

Magic Numbers

 CodeForces - 628D

题意:求区间[l ,r]间偶数位都是d,奇数位都不是d的个数。l和r位数相等。

解:l和r位数相等,很舒服,不用判前导0了。记录一下位数,判断其位置和是不是d即可。多取点模。

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxx 100005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 1000000007
char a[2005];
int len;
ll dp[2005][2005]={0};
int m,d;
ll dfs(ll pos,ll sum,ll limit){
    if(pos==len+1) {
        return sum%m==0;
    }
    if(!limit&&dp[pos][sum]!=-1)
        return dp[pos][sum];
    ll ret=0;
    ll res=limit?a[pos]:9;
    for(int i=0;i<=res;i++){
        if((i==d&&pos%2)||(i!=d&&!(pos%2))) continue;
        ret=(ret+dfs(pos+1,(sum*10+i)%m,limit&&(i==a[pos])))%mod;
    }
    return !limit?dp[pos][sum]=ret:ret;
}
ll solve(){
    len=strlen(a+1);
    for(int i=1;i<=len;i++){
        a[i]-='0';
    }
    return dfs(1,0,1);
}
signed main() {
//    int T;
//    scanf("%d",&T);
//    while(T--) {
//
//    }
    memset(dp,-1,sizeof dp);
    scanf("%d%d",&m,&d);
    scanf("%s",a+1);
    int flag=1;
    ll res=0;
    ll r1=solve();
    for(int i=1;i<=len;i++){
        res=(res*10+a[i])%m;
        if((a[i]==d&&i%2)||(a[i]!=d&&!(i%2))) {
            flag = 0;
        }
    }
    if(res!=0) flag=0;
    scanf("%s",a+1);
    ll r2=solve();
    printf("%lld\n",((r2-r1+mod)%mod+flag)%mod);
    return 0;
}
View Code

The Maths Lecture

 CodeForces - 507D

题意:求有多少n位数(不算前导0),其后缀之一为k的倍数(不包含0)。

解:一个条件一个条件来。先记录一个con,判断这个后缀是不是0(因为要对k取模)。再记录一下前缀,最后的时候判断第一位是不是0。从低位往高位dp,求和的时候记录一下当前位权。全塞进dp数组就行。a数组是debug用的,debug了半天发现自己把now打成n,直接昏过去。

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxx 100005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 2520
char a[1005];
int len;
ll dp[1005][10][2][2][105]={0};
int n,k,m;
ll dfs(ll pos,ll pre,ll con,ll con2,ll sum,ll now){
    if(pos==0) {
        a[pos+1]=pre+'0';
        a[0]='0';
        if(pre&&(con2||(!con&&sum%k==0))){
            printf("");
        }
        return pre&&(con2||(!con&&sum%k==0));
    }
    a[pos+1]=pre==-1?'\0':pre+'0';
    if(pre!=-1&&dp[pos][pre][con][con2][sum]!=-1)
        return dp[pos][pre][con][con2][sum];
    ll ret=0;
    ll res=9;
    for(int i=0;i<=res;i++){
        if(!con&&sum%k==0) con2=1;
        ret=(ret+dfs(pos-1,i,con&&i==0,con2,(sum+(i*now)%k)%k,now*10%k))%m;
    }
    if(pre!=-1) dp[pos][pre][con][con2][sum]=ret;
    return ret;
}
signed main() {
//    int T;
//    scanf("%d",&T);
//    while(T--) {
//
//    }
    memset(dp,-1,sizeof dp);
    scanf("%d%d%d",&n,&k,&m);
    printf("%lld\n", dfs(n,-1,1,0,0,1));
    return 0;
}
View Code

 

标签:数位,pre,ll,pos,二则,sum,dp,define
From: https://www.cnblogs.com/capterlliar/p/16866149.html

相关文章

  • 线性DP
    线性DP例题1:TakandCardsAtCoderARC060ATakandCards有\(n\)个整数。第\(i\)个数的值为\(x_i\)。从这些整数中挑选\(1\)个及以上,使选择的整数的平均数等......
  • Debian 11 安装snap(snapd)之后使用apt(apt-get)安装软件报错"E:Sub-process /usr/bin
    1问题描述与分析为了安装notepad++,安装先安装了snap,貌似失败了,又安装了snapd,sudoaptinstallsnapd#sudoaptinstallsnap然后再用aptinstall时就报错:dpkg-dev......
  • dp-leetcode152
    动态规划问题,存在重叠子问题/***<p>给你一个整数数组<code>nums</code> ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘......
  • Java 线程池之ThreadPoolExecutor学习总结
    前提javaversion"1.8.0_25"池简述软件开发活动中,我们经常会听到数据库连接池、内存池、线程池等各种“池”概念,这些“池”到底是什么东西呢?程序的世界里,我们可以将池简单......
  • Java 线程池之ThreadPoolExecutor学习总结
    前提javaversion"1.8.0_25"池简述软件开发活动中,我们经常会听到数据库连接池、内存池、线程池等各种“池”概念,这些“池”到底是什么东西呢?程序的世界里,我们可以将池简单......
  • [dp 记录]szjudge#26 括号序列
    dp部分平凡,但是后面找最值是值得深思的。题意:给出两个由左右括号形成的字符串,求在长度最小的基础上字典序最小的合法括号序列,使给出字符串均为其子串。\(|s|,|t|\leq30......
  • 批量给UDP_Server发消息
    Server端     客户端:  运行结果: ......
  • NOIP2017 逛公园 记忆化搜索|dp(已过hack数据)
    30pts可以发现,\(k=0\)的情况下,问题转化为最短路计数,即从起点\(s\)到每个点有多少最短路。跑最短路的时候顺便维护\(ans[u]\),表示从\(s\)到\(u\)的最短路方案,讨论如下:①......
  • JavaScript修改修改图片dpi
    欢迎关注前端早茶,与广东靓仔携手共同进阶​​​​前端早茶专注前端,一起结伴同行,紧跟业界发展步伐~ 一、原理changeDPI提供了2个实用函数,可以更改画布生成的图像的dpi,无......
  • JavaScript修改修改图片dpi
    欢迎关注前端早茶,与广东靓仔携手共同进阶​​​​前端早茶专注前端,一起结伴同行,紧跟业界发展步伐~ 一、原理changeDPI提供了2个实用函数,可以更改画布生成的图像的dpi,无......