$BZOJ1799\ Luogu4127$ 月之谜 数位统计$DP$
2024-09-06 16:07:48
Description
Sol
看了很久也没有完全理解直接$DP$的做法,然后发现了记搜的做法,觉得好棒!
这里是超棒的数位$DP$的记搜做法总结 看完仿佛就觉得自己入门了,但是就像文中写的,还是要多做题才能真正弄明白鸭,还要加油(ง •_•)ง
然后这里是同一个人的本题题解
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define il inline
#define Rg register
#define go(i,a,b) for(i=a;i<=b;i++)
#define yes(i,a,b) for(i=a;i>=b;i++)
#define ll long long
#define mem(a,b) memset(a,-1,sizeof(a));
using namespace std;
il ll read()
{
ll x=,y=;char c=getchar();
while(c<''||c>''){if(c=='-')y=-;c=getchar();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
int len,a[];
ll l,r,mod,f[][][];
il ll dfs(int pos,int sum,int ys,int limit)
{
if(pos>len)return (ys== && sum==mod);
if(!limit && f[pos][sum][ys]!=-)return f[pos][sum][ys];
ll as=;int maxs=limit?a[len-pos+]:,i;
go(i,,maxs)as+=dfs(pos+,sum+i,(1LL*ys*+i)%mod,i==maxs&&limit);
if(!limit)f[pos][sum][ys]=as;return as;
}
il ll sol(ll x)
{
len=;
while(x)a[++len]=x%,x/=;
ll as=;
go(mod,,*len){mem(f,);as+=dfs(,,,);}
return as;
}
int main()
{
l=read(),r=read();
printf("%lld\n",sol(r)-sol(l-));
return ;
}
最新文章
- some useful linux commands
- ae工具是一种特殊的命令
- js判断移动端是否安装某款app的多种方法
- linux常用命令:5网络命令
- c# 网络是否连接
- 省常中模拟 Test1 Day1
- Linux Server
- 【.NET】发送Email
- thinkjs 文件上传
- oracle学习笔记(一) oracle 体系结构简单介绍以及创建表空间和用户
- BootstrapTable的列排序怎么搞
- RocketMQ源码分析:(二)消息发送的三种方式
- mac sourcetree push分支选中所有tag的时候报错
- Spring Boot 1.5.10 发布:修复重要安全漏洞!!!
- 使用openpyxl实现excel文件的读取操作
- swiper4 一个页面多个轮播
- hdu1002-A + B Problem II-(java大数)
- swiper监听左滑还是右滑动
- keil5配置stm32库函数开发
- Mac下TensorFlow安装及环境搭建