当前位置: 首页 > news >正文

解题报告-泥路(muddyroad.*)

泥路(muddyroad.*)

题目背景

yxr 热爱多级跳,而且他十分喜欢在泥路上练习多级跳。

不幸的是,有一天下雨了,yxr 穿着的却是一双新的鞋子。yxr 心疼自己的鞋子,但是又不舍得放弃练习多级跳,于是他决定先勘察泥路。

题目描述

yxr根据他丰富的经验得出了一个结论:泥地可以均等分成 \(N+1\) 部分,从 \(0\) 开始编号,一直编号到 \(n\),设每部分一个单位长度。

每部分泥地可以分成两种情况,积水或者没有积水。由于跳得越远,用的力就越大。yxr 发现,如果自己由远于 \(D_1\) 单位长度的地方跳到没有积水的泥地里面泥地会被破坏;如果自己由远于 \(D_2\) 单位长度的地方跳到有积水的泥地里面泥地里面的水才会溅到 yxr 的鞋子上。幸运的是 yxr 选定的 \(0\) 号泥地没有积水。

yxr 当然不愿意破坏这一片和自己拥有美好感情的泥地,于是他决定自己不会由远于 \(D_1\) 单位长度的地方跳到没有积水的泥地;另外 yxr 也不愿意弄脏自己的新鞋,他也决定不会由远于 \(D_2\) 单位长度的地方跳到有积水的泥地。

于是他自己算了算自己有多少种方法在满足上述条件的情况下,恰好从 \(0\) 号泥地跳到 \(N\) 号泥地,发现方案数 \(K\) 是个奇数,于是他很高兴地练习了起来。

在 yxr 练习完成之后,发现泥地完全干了,但是他很怀念积水的泥地,但是却忘记了哪些地方是有积水的。他努力回忆,记得 \(N\) 部分之中有 \(M\) 部分是积水的,也记得自己曾经算过的方法数 \(K\) 是个奇数,但是不记得是什么了,毕竟方法数很大啊。

于是他想知道,有多少种长度为 \(N+1\) 的泥地,满足恰好 \(M\) 部分积水,且 \(0\) 号泥地没有积水,而且满足 yxr 算过的练习方案数 \(K\) 是奇数。

输入描述

输入仅有四个整数 \(N\)\(M\)\(D_1\)\(D_2\),如题目描述。

输出描述

输出仅包含一个整数,表示方案数,结果对 \(10^9+7\) 取模。

输入输出样例#1

输入样例#1

5 1 2 0

输出样例#1

2

输入输出样例#2

输入样例#2

9 2 3 1

输出样例#2

24

说明/提示

样例#1解释

对于样例一,泥地有如下两种( \(0\) 号位置省略),“\(\text{B}\)”表示有积水,"\(\text{A}\)" 表示没有积水。

\(\text{AAABA}\) 练习方案数为 \(3\)

\(\text{BAAAA}\) 练习方案数为 \(3\)

数据范围

  • 对于 \(20\)% 的数据,\(M=0\)
  • 对于另外 \(20\)% 的数据 \(N \leq 15\)\(M \leq 5\)\(D_1 \leq 5\)
  • 对于 \(60\)% 的数据 \(N \leq 120\)\(M \leq 12\)\(D_1 \leq 10\)
  • 对于 \(70\)% 的数据 \(N \leq 300\)\(M \leq 20\)\(D1 \leq 12\)
  • 对于 \(100\)% 的数据 \(N \leq 500\)\(M \leq 20\)\(D1 \leq 20\)
  • 对于 \(100\)% 的数据 \(20 \geq D1 \geq D2 \geq 0\)

解题报告

神秘状压DP题目,就算补发了一些提示,拼尽全力也只能拿到 \(90 \text{pts}\)

对于求方案数的题目,很容易想到用 DP 求解。显然,最棘手的就是如何在转移的过程中保证跳跃方法数为奇数。

先定义一个函数 \(g(i)=1\)\(0\),表示跳到第 \(i\) 个位置的方案数的奇(\(1\))偶(\(0\))性。

这个函数有什么用?答曰:它可以通过递推来计算出来

下面简单讲讲怎么递推。

显然,跳到第 \(i\) 个位置的方案数由两部分相加:

  • \(i\) 个位置不是水坑时的方案数,等于所有距离不超过 \(D_1\) 的位置的方案和。
  • \(i\) 个位置是水坑时的方案数,等于所有距离不超过 \(D_2\) 的位置的方案和。

显然,只有所加的方案数里有奇数个奇数相加时,跳到第 \(i\) 个位置的方案数才为奇数。

对应到函数 \(g(i)\) 上,只有所有符合条件的 \(g(j)\) 的和为奇数时,\(g(i)\) 才为 \(1\),更进一步,\(g(i)\) 就是把所有符合条件的 \(g(j)\) 全部异或起来的结果(即 \(g(i)\) 为所有符合条件的 \(g(j)\) 的异或和)

这时我们还发现,\(20 \geq D_1 \geq D_2\),于是就有一个想法:我们可以把连续 \(D_1\) 个位置的 \(g(i)\) 状压,进行状压 DP。

我们设状态数组 \(dp[i][j][k]\),表示进行完了第 \(i\) 位,已经放了 \(j\) 个水坑,之前连续 \(D_1\) 个位置的 \(g(i)\) 状压后的掩码为 \(k\)

\(B_1=2^{D_1}-1\)\(B_2=2^{D_2}-1\),后面用于得出距离不超过 \(D_1\)\(D_2\) 的位置的 \(g(j)\) 的状态,定义函数 \(\text{popcount}(k)\) 为状态掩码 \(k\)\(1\) 的个数,从上面的分析可以看出,\(\text{popcount}(k) \mod 2\)\(\text{popcount}(k) \and 2\),就是 \(g(i)\)

下面给出状态转移方程,方法是计算当前状态对之后状态的贡献:

  • 如果第 \(i\) 为水坑,那么 \(dp[i+1][j+1][ (k<<1)\and B_1 \or (\text{popcount}(k\and B_1)\and1) ]+=dp[i][j][k]\)
  • 如果第 \(i\) 不为水坑,那么 \(dp[i+1][j][ (k<<1)\and B_1 \or (\text{popcount}(k\and B_2)\and1) ]+=dp[i][j][k]\)

其中:

  • \((k<<1)\and B_1 \or (\text{popcount}(k\and B_{0/1})\and1)\)”都是新状态的计算方法。
  • "\(\and B_1\)" 是为了保证新状态的掩码不超过 \(D_1\) 位。
  • \(\text{popcount}(k\and B_{0/1})\and1)\)” 是在计算 \(g(i)\)
  • \((k<<1)\or (\text{popcount}(k\and B_{0/1})\and1)\)“是在把 \(g(i)\) 添加进新的状态掩码中。

相信这个方程还是很显然的。

这时其实就几乎做完了,但由于理论状态数是 \(N\times M\times 2^{D_1}\),时间和空间的复杂度都不可接受,于是还有以下优化:

  • 由于 \(dp[i][j][k]\) 只与 \(dp[i-1][j'][k']\) 有关,可以将关于 \(i\) 的维度写成滚动数组,减小空间复杂度。
  • 对于每个确定的 \(i\)\(j\) 实际用到的 \(k\) 会很少,于是就可以哈希以下 DP 状态,减小时间复杂度。

不过作者不会哈希 DP 状态,所以只得到了 \(90\) 分,以下是这个 \(90\text{pts}\) 的代码:

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=(1E+9)+7;
const int N=501;
const int M=21;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )
#define add(x,y) ( x=(x+y)%mod )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}int n,m,d1,d2,b1,b2;
int dp[2][M][1<<M];inline int calc(int x)
{int tmp=0;while(x){tmp^=1;x-=(x&(-x));}return tmp;
}signed main()
{freopen("muddyroad.in","r",stdin);freopen("muddyroad.out","w",stdout);n=read(),m=read(),d1=read(),d2=read();if(!n){printf("%d\n",(int)!m);return 0;}b1=(1<<d1)-1,b2=(1<<d2)-1;dp[0][0][1]=1;for(int i=0;i<n;i++){for(int j=0;j<=m;j++)for(int k=0;k<=b1;k++)dp[(i+1)&1][j][k]=0;for(int j=0;j<=m;j++)for(int k=0;k<=b1;k++){if(!dp[i&1][j][k]) continue;int pos=( (k<<1)&b1 )|calc(k);add(dp[(i+1)&1][j][pos],dp[i&1][j][k]);if(j<m){pos=( (k<<1)&b1 )|calc(k&b2);add(dp[(i+1)&1][j+1][pos],dp[i&1][j][k]);}}}int ans=0;for(int k=0;k<=b1;k++)if(k&1) add(ans,dp[n&1][m][k]);printf("%d\n",ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=20074

相关文章:

  • 洛谷P10112 [GESP202312 八级] 奖品分配
  • P10400 『STA - R5』消失的计算机
  • 2025 地坪研磨机厂家推荐权威推荐排行榜:品牌深度解析及格力 / 宁德时代合作案例速递水磨石/遥控式/座驾式/小型地坪研磨机厂家推荐
  • 2025 年最新推荐铝塑膜源头厂家权威排行榜:聚焦 3000㎡厂房与完整产业链的优质企业盘点复合/防锈防潮/木箱包装/设备包装铝塑膜厂家推荐
  • 2025 年真空袋生产厂家最新权威推荐排行榜:TOP 级企业工艺、服务及适配场景全景对比指南木箱/设备/海运防潮/铝塑/电柜真空袋厂家推荐
  • 《码界飞升传II:数据星辰异界问道》
  • Win FAQ
  • 结论(数学)
  • loki收集容器日志
  • Xcode 火焰图
  • 完整教程:dlib库关键点定位和疲劳检测
  • 2025 长沙美食餐厅权威推荐排行榜:老店红记领衔新晋品牌,200 + 湘味与网红菜品深度解析,吃货必藏指南长沙美食湘菜馆 /大排档/网红店餐厅推荐
  • VKD233HH触控IC有两种输出方式“直接输出”和“锁存输出”单路触摸检测芯片
  • 打包present, but unavailable
  • 2025 年最新推荐环保门禁厂家权威排行榜:清洁运输 / 智能 / 移动源系统及电子台账厂商详析企业/智能环保门禁厂家推荐
  • 2025 年即时通讯公司推荐 小天互连:私有化部署即时通讯、信创即时通讯、国产化即时通讯、局域内网即时通讯、企业 IM 即时通讯解决方案解析
  • GJOI 模拟赛6、7部分题解
  • 【C++list】底层结构、迭代器核心原理与常用接口完成全解析
  • 完整教程:Flink Watermark机制解析
  • 2025 年北京湖南菜餐厅推荐:小湖南岸以湖湘本味与匠心服务,成京城湘菜口碑之选
  • Vector
  • SSM
  • Mybatis Plus
  • 0927模拟赛总结
  • AT_agc010_b [AGC010B] Boxes
  • Selenium自动化脚本总报错?这7个调试技巧帮你解决90%问题
  • C语言 - *进制转*进制 3
  • ThreadLocal详解
  • C语言 - *进制转*进制 2
  • Functions