「题解」小a和小uim之大逃离
小a和uim来到雨林中探险。突然一阵北风吹来,一片乌云从北部天边急涌过来,还伴着一道道闪电,一阵阵雷声……
一 题目
描述
小a和uim来到雨林中探险。突然一阵北风吹来,一片乌云从北部天边急涌过来,还伴着一道道闪电,一阵阵雷声。刹那间,狂风大作,乌云布满了天空,紧接着豆大的雨点从天空中打落下来,只见前方出现了一个披头散发、青面獠牙的怪物,低沉着声音说:“呵呵,既然你们来到这,只能活下来一个!”。小a和他的小伙伴都惊呆了!
瞬间,地面上出现了一个n*m的巨幅矩阵,矩阵的每个格子上有一坨0~k不等量的魔液。怪物各给了小a和uim一个魔瓶,说道,你们可以从矩阵的任一个格子开始,每次向右或向下走一步,从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液,下一步由uim吸收,如此交替下去,并且要求最后一步必须由uim吸收。魔瓶只有k的容量,也就是说,如果装了k+1那么魔瓶会被清空成零,如果装了k+2就只剩下1,依次类推。怪物还说道,最后谁的魔瓶装的魔液多,谁就能活下来。小a和uim感情深厚,情同手足,怎能忍心让小伙伴离自己而去呢?沉默片刻,小a灵机一动,如果他俩的魔瓶中魔液一样多,不就都能活下来了吗?小a和他的小伙伴都笑呆了!
现在他想知道他们都能活下来有多少种方法。
输入
第一行,三个空格隔开的整数n,m,k
接下来n行,m列,表示矩阵每一个的魔液量。同一行的数字用空格隔开。
输出
一个整数,表示方法数。由于可能很大,输出对1 000 000 007取余后的结果。
1 | 对于20%的数据,n,m<=10,k<=2 |
二 题解
题外话:这是蒟蒻的第三百道题,同时是本站的第二十篇文章。
50分算法还是很好想出来的。
设$f_{i,j,p,q,0/1}$表示当前以格子$(i,j)$为终点,小a收集了$p$体积的魔液,小uim收集了$q$体积的魔液,且上一步是小a($0$)还是小uim($1$)走 的时候,所得到的方案数。
边界条件是枚举起点(小a走出第一步的点),且方案为$1$。
可惜内存会炸掉。
我们发现转移状态只需要用到$p,q$的差值,所以记录$p,q$的值是很不划算的。
设$v=p-q$,可以得到一个更优秀的状态设计:
设$f_{i,j,v,0/1}$表示当前以格子$(i,j)$为终点,小a与小uim收集的魔液的体积之差等于$v$,且上一步是小a($0$)还是小uim($1$)走 的时候,所得到的方案数。
但是差值有负数。因为差值的取值范围在$-k \text{~} k$,所以有一个很朴素的想法是把每个差值加上$k$来避免负数。但是这么大的空间还是有炸掉的危险。
其实继续研究就可以发现,根本不需要这么麻烦。因为即使是这个差值也是要模上$k+1$的,所以余数最多有$k+1$种情况。
对于差值为负的情况,我们把它加上一个模数($k+1$)再模,让余数总为正数。
此时可以形象的理解一下:小uim的魔液比小a多,小a不服气,又拿来一瓶刚好溢出的魔液,把小uim又比下去了。
因为题目的特殊性质,总满足$k+1=0$,所以并不会出问题。
方程:
$$\begin{align} f_{i,j,v,0} = f_{i-1,j,v-s_{i,j},1} + f_{i,j-1,v-s_{i,j},1} \newline f_{i,j,v,1} = f_{i-1,j,v+s_{i,j},0} + f_{i,j-1,v+s_{i,j},0} \end{align}$$
其中$s_{i,j}$是格子$(i,j)$的魔液体积。
还有一个小坑:虽然余数是long long型的,但是转移状态必须用int,统计状态再用long long,不然MLE。并且此时还不能让int自然溢出,还必须模上一个long long型的余数,不然有神仙错误……
附上代码
1 |
|
「题解」小a和小uim之大逃离