P4999 烦人的数学作业

在这里插入图片描述
不会数位dp,遂来补习
题意:给定区间 [ L , R ] [L,R] [L,R]求这个区间每个数字拆成10进制后的数字和.
按照固定套路,先要解决 0 到 n 0到n 0n每个数字拆成10进制后的数字和.
然后把 n n n拆成一个长度为 l e n len len的串, d f s dfs dfs找到合法的 l e n len len位置上的合法解并且记录下来.
具体方法为 d f s ( c u r , s u m , t o p ) dfs(cur,sum,top) dfs(cur,sum,top)表示当前在 c u r cur cur位,和是 s u m sum sum,是否贴着上界 t o p top top
之后当前 c u r cur cur位能取的数字有两种情况:
1. t o p top top 1 1 1,之前的情况已经贴着了,所以只能取 0 到 a [ c u r ] 0到a[cur] 0a[cur].
2. t o p top top 0 0 0,之前取数没有贴着上界,所以取数范围是 0 到 9 0到9 09.
如果当前是 t o p = = 1 & & i = = a [ c u r ] top==1\&\&i==a[cur] top==1&&i==a[cur],那么下一个状态就会贴着上界,否则就不是贴着上界的状态.
d f s dfs dfs求解数位dp的情况,贴着上界的情况的讨论十分重要.

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
ll mod = 1e9+7;int a[20];
ll dp[20][200][2];
int dfs(int cur,int sum,bool top){if(cur==0) return sum;ll &ans = dp[cur][sum][top];if(ans!=-1) return ans;ans = 0;int bound = (top==1) ? a[cur] : 9;for(int i=0;i<=bound;i++){ans = ( ans+dfs(cur-1,sum+i,(top==1&&i==bound))%mod)%mod; }return ans%mod;
}
ll solve(ll n){memset(dp,-1,sizeof(dp));int len = 0;while(n) a[++len] = n%10,n/=10;return dfs(len,0,1)%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){ll L,R;cin>>L>>R;cout<<(((solve(R)-solve(L-1))%mod+mod)%mod)<<"\n";}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/48184.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微机作业——“学生成绩统计“

微机作业——“学生成绩统计” 1. 题目 从键盘输入某计算机应用班35人的《计组》成绩&#xff08;百分制&#xff09;&#xff0c;按成绩从高到低排序。并计算全班总成绩、平均成绩、统计低于平均成绩的学生人数&#xff0c;并将结果在屏幕上显示。 2. 实现功能 从键盘输入…

CRNN论文翻译——中英文对照

文章作者&#xff1a;Tyan 博客&#xff1a;noahsnail.com | CSDN | 简书 声明&#xff1a;作者翻译论文仅为学习&#xff0c;如有侵权请联系作者删除博文&#xff0c;谢谢&#xff01; 翻译论文汇总&#xff1a;https://github.com/SnailTyan/deep-learning-papers-tra…

CTPN论文翻译——中英文对照

文章作者&#xff1a;Tyan 博客&#xff1a;noahsnail.com | CSDN | 简书 声明&#xff1a;作者翻译论文仅为学习&#xff0c;如有侵权请联系作者删除博文&#xff0c;谢谢&#xff01; 翻译论文汇总&#xff1a;https://github.com/SnailTyan/deep-learning-papers-tra…

轻松使用阿里达摩院开源在魔搭社区上的CLUE语义匹配模型

作者&#xff1a;燕返 简介 CLUE&#xff08;中文语言理解测评基准&#xff09;是中文语言理解领域的权威榜单&#xff0c;包含多项测评任务。近日&#xff0c;达摩院NLP团队在其中的语义匹配榜登顶&#xff0c;并在魔搭社区&#xff08;ModelScope&#xff09;上开源了预训练和…

重要升级!OpenAI PowerShell SDK 支持Azure OpenAI的ChatGPT服务

如果关注过我这个公众号&#xff0c;你可以通过这篇文章&#xff08;ChatGPT PowerShell SDK 发布 &#xff09; 了解到我开发和维护的这个非官方的OpenAI PowerShell SDK, 此前已经支持在PowerShell中发起completions服务调用&#xff08;可广泛用于后台自动化&#xff0c;主要…

[chatgpt+Azure]unity AI二次元小女友之使用微软Azure服务实现RestfulApi->语音识别+语音合成

1.简述 如题所述&#xff0c;这个小项目是在unity引擎端&#xff0c;使用了chatgpt微软azure的一个AI二次元女友对话的项目&#xff0c;实现原理也比较简单&#xff0c;即在unity端实现AI二次元女友的交互界面&#xff0c;接入chatgpt-3.5-turbo的api接口&#xff0c;借助chatg…

chatgpt 能用什么到底

l理论上gpt可以担任一个很好的方向指导GPT社区

微信导出表情包教程

方法1&#xff1a;微信公众号 去免费申请个微信公众号&#xff0c;然后关注就可以给公众号发送表情包了&#xff0c;然后就可以下载这个表情包。 方法二&#xff1a;微信网页版 登录 https://wx.qq.com/ 然后聊天发送的表情直接拉出页面就会生成新的表情包页面&#xff0c;然后…

简单操作,轻松在线制作gif动图表情包

相信很多的朋友在使用微信、QQ等工具聊天的时候&#xff0c;经常会用到各式各样的表情包。表情包不但更加的有趣&#xff0c;而且能传达出很多文字无法表达的感情和情绪&#xff0c;更加的生动形象。那么大家知道怎么gif制作https://www.gif.cn/动图的吗?接下来手把手教大家怎…

表情包的gif怎么制作?一招教你快速做gif表情

Gif表情包是当下网友们聊天必备的一种情感表达方式&#xff0c;利用一张有动态效果的图片就可以表达出自己的心情和想法&#xff0c;十分有趣。那么&#xff0c;大家一定很好奇自己应该如何制作gif动图表情包吧&#xff01;很简单&#xff0c;使用gif制作&#xff08;https://w…

从微信导出表情包的简便方法 (不使用微信 for pc,无需进入文件夹寻找!)

微信表情大概分为两类&#xff0c;一类是打开右下角有一个可以操作的按键可以保存&#xff0c;一般是做好一套可以下载的但大多数没有杀伤力&#xff0c;为江湖人所不齿&#xff0c;另一件是没有的&#xff0c;本文从&#xff08;技术角度&#xff09;讨论后一个 不使用微信 f…

怎么做表情包微信gif?好用的制作方法介绍

怎么做表情包微信gif&#xff1f;现如今基本上人手一个微信&#xff0c;微信作为我们日常人际沟通的重要工具之一&#xff0c;我们在日常的聊天中&#xff0c;除了发送文字、图片等内容&#xff0c;也会发送一些表情包&#xff0c;活跃气氛。通常情况下&#xff0c;我们发送的表…

LM+Embedding构建问答系统的局限性及优化方案

原文&#xff1a;LLMEmbedding构建问答系统的局限性及优化方案 - 知乎 近期 LangChain LLM 方案高速发展&#xff0c;降低了知识问答等下游应用的开发门槛。但随着业务深入&#xff0c;一些局限性也日渐显露&#xff0c;比如&#xff1a;LLM意图识别准确性较低&#xff0c;交互…

Segment Anything CV界的GPT—prompt-based里程碑式研究成果

一、计算机视觉界的里程碑式研究成果 - SAM与SA-1B综述 Segment Anything受chatGPT式的prompt-based思路启发&#xff0c;训练数据集涵盖10亿masks&#xff0c;根据提供的图片注释实时产生不同的mask分割结果&#xff0c;试用效果惊人。 Segment Anything之于Computer Vision&…

更快地分割任何事物:面向移动应用的轻量级Sam

文章目录 摘要1、简介2、相关工作3、适合移动设备的SAM3.1、背景和项目目标3.2、提出方法4、实验4.1、实验设置4.2、MobileSAM的性能与原版SAM相当4.3、MobileSAM优于FastSAM5、结论摘要 https://arxiv.org/pdf/2306.14289v2.pdf 分割任何事物模型(SAM)因其令人印象深刻的零样本…

基于自然语言处理的多模态模型_综述

A Survey on Multimodal Large Language Models&#xff1b; 论文链接&#xff1a;https://arxiv.org/pdf/2306.13549.pdf 项目链接(实时更新最新论文&#xff0c;已获1.8K Stars)&#xff1a;https://github.com/BradyFU/Awesome-Multimodal-Large-Language-Models 研究背景 …

AI向百万薪资 高级原画师开刀?!爆Midjourney入局3D模型生成

来源 SoulofArt | ID Soul_Art 现在AI向高级原画师和3D开刀了&#xff1f; 网传爆料AI已入局3D模型生成... 这进化速度放在整个行业都十分炸裂 4月&#xff0c;Midjourney进一步宣布推出Niji-journey V5 这是MJ针对二次元动漫风格预训练好的模型 可在其中添加提示词直接调…

Java 20 正式发布,超神了。。

出品 | OSC开源社区&#xff08;ID&#xff1a;oschina2013) ChatGPT王炸更新&#xff01;终于解封了... 老铁们&#xff0c;JDK 20 / Java 20 正式发布了&#xff0c;这版本号简直超神了。。 JDK 20 是一个短期维护版本&#xff0c;将获得六个月的支持。尽管如此&#xff0c;但…

JDK 20 正式发布, JDK 21 最新动态来了

点击“开发者技术前线”&#xff0c;选择“星标” 让一部分开发者看到未来 来自 infoQ | OSC开源社区&#xff08;ID&#xff1a;oschina2013) JDK 20 是自 JDK 17, 以来的第三个非长期支持&#xff08;LTS&#xff09;版本&#xff0c;正如甲骨文 Java 平台组的首席架构师 Ma…

Ubuntu安装spark时遇到的问题及解决方案

伪分布式模式配置&#xff1a; 安装SSH: 问题一&#xff1a;安装openssh-server时出现以下报错 Package openssh-server has no installation candidate 出错原因: 一开始以为是apt命令没更新&#xff0c;apt-get update之后发现还是安装不了&#xff0c;可能是 文件/etc/apt…