[LUOGU3413] SAC#1 - 萌数
2024-09-01 11:48:54
题目背景
本题由世界上最蒟蒻最辣鸡最撒比的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行,包含一个整数,即为答案。
输入输出样例
说明
记n为r在10进制下的位数。
对于10%的数据,n <= 3。
对于30%的数据,n <= 6。
对于60%的数据,n <= 9。
对于全部的数据,n <= 1000,l < r。
随便写写
f[i][j][k][0/1],决策到第i位,上一位的数字是j,上上位的数字是k,是否曾经出现过回文串, 的总数。
然后就记忆化搜索一下,记得判断前一位和前前一位是否合法...
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
inline int read() {
int res=;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();
return res;
}
#define reg register
#define mod 1000000007
int l, r; int f[][][][];
int wei[], cnt; inline int dp(int pos, int lst1, int lst2, bool hav, bool flag, bool fir, bool sec)
{ //是否有限制
if (pos == ) return hav;
if (!fir and !sec and !flag and f[pos][lst1][lst2][hav] != -) return f[pos][lst1][lst2][hav] % mod;
int lim = flag ? wei[pos] : ;
int ans = ;
for (reg int i = ; i <= lim ; i ++)
{
if (i == lst1 and !fir) ans = (ans + dp(pos - , i, lst1, , flag && i == wei[pos], fir && i == , sec && lst1 == )) % mod;
else if (i == lst2 and !fir and !sec) ans = (ans + dp(pos - , i, lst1, , flag && i == wei[pos], fir && i == , sec && lst1 == )) % mod;
else ans = (ans + dp(pos-, i, lst1, hav, flag && i == wei[pos], fir && i == , sec && lst1 == )) % mod;
}
if (!flag and !fir and !sec) f[pos][lst1][lst2][hav] = ans % mod;
return ans % mod;
} signed main()
{
memset(f, -, sizeof f);
int res1 = , res2 = ; string a;
cin >> a;
cnt = ;
for (reg int i = a.length() - ; i >= ; i --) wei[++cnt] = a[i] - '';
int k = ;
if (wei[]) wei[]--;
else {while(wei[k] == ) wei[k] = , k++; wei[k]--;} res1 = dp(cnt, , , , , , ) % mod; cnt = ;
cin >> a;
for (reg int i = a.length() - ; i >= ; i --) wei[++cnt] = a[i] - '';
res2 = dp(cnt, , , , , , ) % mod; printf("%lld\n", (res2 - res1 + mod) % mod);
return ;
}
最新文章
- python脚本利用windows计划定时执行
- Beautiful 疑问小记
- win7和win8如何设置快速启动栏
- QMessageBox 在MAC下更加自然
- c++内存中字节对齐问题详解
- MAC下编译FFMPEG
- 基于.NET平台的分布式应用程序的研究
- app包中的fragment和v4包中的fragment的使用的区别
- 从源代码分析modelDriven拦截器和params拦截器和拦截器prepare 和paramsPrepareParamsStack拦截器栈(让你的Struts2代码更简洁——如何培养框架设计能力
- Linux常用命令3--如何设置IP地址?如何更改系统时间?
- Excel 按模板格式导出
- chrome主页被篡改 成hao123
- [八省联考2018] 劈配 mentor
- Mui Webview下来刷新上拉加载实现
- Windows API编程(SDK编程)配置VS2017——出现LNK 2019错误的win32项目如何解决
- 自托管websocket和webapi部署云服务器域名及远程访问
- iOS 判断当前网络状态的三种方法
- tkinter调取签名网而设计签名页面(十七)
- 转载:JAVA序列化与反序列化 (作者:YSOcean)
- Windows下 VS2015编译ForestDB
热门文章
- application.properties 乱码 (已验证)
- FJUT2019暑假周赛三部分题解
- 使用Bookinfo应用测试Kuma服务网格
- 第一次作业:使用Packet Tracer分析HTTP包
- Day 10 用户的提权,用户组的创建删除
- 让我们一起学习如何使用AIDL,它其实并不难(Android)
- 实现一个正则表达式引擎in Python(三)
- python unittest+parameterized,单元测试框架+参数化
- 格子游戏Grid game CodeForce#1104C 模拟
- Java入门系列之hashCode和equals(十二)