P3413 SAC#1 - 萌数

    • 75通过
    • 303提交
  • 题目提供者ProjectWTA
  • 标签 动态规划,动规,dp 数位动规,数位dp 洛谷原创
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。

    寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd

    题目描述

    辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!

    好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。

    现在SOL想知道从l到r的所有整数中有多少个萌数。

    由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。

    输入输出格式

    输入格式:

    输入包含仅1行,包含两个整数:l、r。

    输出格式:

    输出仅1行,包含一个整数,即为答案。

    输入输出样例

    输入样例#1: 复制
    1 100
    输出样例#1: 复制
    10
    输入样例#2: 复制
    100 1000
    输出样例#2: 复制
    253

    说明

    记n为r在10进制下的位数。

    对于10%的数据,n <= 3。

    对于30%的数据,n <= 6。

    对于60%的数据,n <= 9。

    对于全部的数据,n <= 1000,l < r。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。