Luogu P5307 [COCI2019] Mobitel
2024-08-26 22:34:51
题意
有一个 \(r\times c\) 的矩阵 \(a\),矩阵的每个位置都有一个正整数,求从左上角走到右下角并且满足路径上数字乘积之和大于 \(n\) 的方案数。
\(\texttt{Data Range:}1\leq r,c\leq 300,1\leq n\leq 10^6\)
题解
本人的本命题居然是个 DP + 整除分块呢。
草哦为什么这个题目名字叫手机啊我怎么看了半天没有看出与手机的任何关联呢
首先考虑一个非常 naive 的 DP,设 \(f_{i,j,k}\) 表示在 \((i,j)\) 位置,已经走过的路径乘积之和为 \(k\) 的方案数,那这个东西很明显由于复杂度上天显得非常不可做。
于是我们可以换个方向去思考这个问题,设 \(f_{i,j,k}\) 表示在 \((i,j)\) 位置还需要乘上 \(k\),路径的乘积才能超过 \(n\),这样子的话转移其实也很好写,但是毕竟状态的数量还是太庞大了,复杂度依旧上天。
这个时候注意到 \(k\) 这个维度上的取值很少,根据整除分块的理论只会有 \(O(\sqrt{n})\) 种,所以可以考虑对所有真正有用的值来 DP,这个时候只需要预处理出每一个可能的取值对应哪个块即可做到 \(O(rc\sqrt{n})\)。
注意到这东西空间会超,所以考虑对 \(i\) 这一位滚一下就好了。同时,代码细节贼多,稍不注意就会挂成狗。这个版本的代码跑的贼慢,看看到时候来卡卡常什么的。
代码
#include<bits/stdc++.h>
#define dv(x,y) ((x)/(y)+!!((x)%(y)))
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=1e6+51,MOD=1e9+7;
ll r,c,n,blkc;
ll x[351][351],d[MAXN],rv[MAXN],f[2][351][2051],blk[2051];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
int main()
{
r=read(),c=read(),n=read();
for(register int i=1;i<=r;i++)
{
for(register int j=1;j<=c;j++)
{
x[i][j]=read();
}
}
for(register int i=1;i<=n;i++)
{
(d[i]=dv(n,i))!=d[i-1]?blk[++blkc]=d[i],rv[d[i]]=blkc:1;
}
f[1][1][rv[dv(n,x[1][1])]]=1;
for(register int i=1;i<=r;i++)
{
for(register int j=1;j<=c;j++)
{
for(register int k=1;k<=blkc;k++)
{
if(i!=r)
{
ll &s=f[(i&1)^1][j][rv[dv(blk[k],x[i+1][j])]];
s=(s+f[i&1][j][k])%MOD;
}
if(j!=c)
{
ll &s=f[i&1][j+1][rv[dv(blk[k],x[i][j+1])]];
s=(s+f[i&1][j][k])%MOD;
}
(i!=r||j!=c||k!=blkc)?f[i&1][j][k]=0:1;
}
}
}
printf("%d\n",f[r&1][c][blkc]);
}
最新文章
- HTML5的属性
- 数据分析 - 斯特鲁普效应(Stroop effect)
- Xcode 7如何 免费 真机调试iOS应用
- Docker Compose—简化复杂容器应用的利器
- GPS定位原理
- 如何查看hadoop与hbase的版本匹配关系
- Kettle汇总时参数
- CSS入门基础
- codevs1404字符串匹配
- android studio error configuration with name default not found
- FIR数字滤波器的设计要点
- 201521123056 《Java程序设计》第9周学习总结
- shellb编程 之 实践出真知
- Android开发 ---基本UI组件5:监听下拉选项,动态绑定下拉选项、全选/反选,取多选按钮的值,长按事件,长按删除,适配器的使用,提示查询数据,activity控制多按钮
- HTML中的文本标签
- Shell变量相关
- TessorFlow学习 之 神经网络的构建
- .netcore webapi iis 虚拟目录下载apk文件
- java通过poi编写excel文件
- 用.NET WebService Studio调试Web Service解决SOAPAction的问题
热门文章
- Android Studio 自定义字体显示英文音标
- 一篇文章带你了解Java OOP思想
- 简化ETL工作,编写一个Canal胶水层
- 089 01 Android 零基础入门 02 Java面向对象 02 Java封装 01 封装的实现 03 # 088 01 Android 零基础入门 02 Java面向对象 02 Java封装 01 封装的实现 03 使用包进行类管理(1)——创建包
- C++ 关键字 enum
- sprintf_s() 、sprintf()和printf()区别和用法
- 2020已经过去五分之四了,你确定还不来了解一下JS的rAF?
- 远程IO
- 编程福利:50本C语言电子书,你还怕没书看吗!
- 【原创】xenomai3.1+linux构建linux实时操作系统-基于X86_64和arm