首页 > 其他分享 >[ARC171E] Rookhopper's Tour 题解

[ARC171E] Rookhopper's Tour 题解

时间:2024-02-12 22:12:20浏览次数:31  
标签:黑色 ARC171E 白色 题解 ll 石头 Tour 移动 我们

题目链接

首先把 \(m=2\) 和 \(m\) 为奇数的情况判掉,由于我们要对合法的摆放方案计数,而一个摆放方案要判断合法性就必须通过一组合法的移动过程,对移动的状态进行记录以此转移和优化显然没啥前途,因此我们考虑摆放方案和移动过程之间的联系。

一个比较显然的观察是摆放方案和移动过程是一组双射,移动显然能还原唯一一组摆放,那反过来呢?我们只要考虑移动过程形成的环能不能逆着走就行,你尝试构造会发现这个摆放方案其实比较唯一而且不合法。

那接下来我们就开始对移动过程计数,同样此时也出现了一个问题:什么样的移动方案是合法的?

对白色石头的限制是任意两个白色石头都不能出现在同一行或者同一列,如果你有尝试画出路线就会发现这引出了一条对于路线的限制:跳过一个白色石头之后必然要拐弯,原因显然,也就是说我们其实是在交错横向纵向移动,这其实启发我们把两个维度拆开考虑。

而两个白色石头能出现在同一行或者同一列,我们会想去思考:那移动过程中的两个黑色石头能不能出现在同一行或者同一列?

为了引出这个这个条件,我们尝试把黑色和白色石头捆绑考虑,和一个黑色石头捆绑的那个白色石头的位置取决于黑色石头移动过来的方向,再画画图,会发现这个黑色石头再纵向移动的时候其实还带来了一个在这一列的白色石头,如果我们只看行这一位其实这个横向移动带来了在这个方向上的两个障碍,读者可以画画图自己感受一下。

也就是说,我们每次横向移动的黑色石头不能与前面的黑色石头重合,也不能和前面那个跳过的白色石头重合,但前面这个白色石头的相对位置是不确定的,这为我们计数带来了一些困难。

先整理一下情况,现有的条件要求我们对一个大概是选出若干个横坐标表示每次移动到这个坐标,然后这些坐标及其带来的附加东西不能重合,这个附加东西和坐标组成一个大小为 2 的块,然后我们要对这个东西组成的序列计数。

整理完之后就会发现其实我们只要把那一堆看做一个大小为 2 的块然后求在序列里面放这个东西不能重叠的方案数就好了,因为序列是有遍历顺序的,一个顺序就唯一确定了黑色和白色石头的相对位置,跟原本的移动路径就是双射。

最后还有一点小问题,就是我们回到最开始的那个黑色块所带来的白色块的位置是不确定的,我们枚举它,然后就要求在一行里面放下若干个长度为 2 的块,不能重叠,块有标号且最大标号的块一定在我们枚举的那个方向,组合数随便算算就行,记得最后答案乘二,因为我们不知道是先走横的还是先走竖的。

ll solve(ll n,ll m,ll x){
	ll ans=0;
	for(ll i=0;i<m;i++){
		ans=(ans+(i*fac[m-2]%mod)*(C(x-2-i,i)*C(n-x-(m-i-1),m-i-1)%mod))%mod;
		ans=(ans+((m-i-1)*fac[m-2]%mod)*(C(x-1-i,i)*C(n-x-1-(m-i-1),m-i-1)%mod))%mod;
	}
	return ans;
}
int main(){
	ll n=read(),m=read(),a=read(),b=read();prework();
	if(m&1 || m==2){cout<<0;return 0;}
	cout<<(solve(n,m/2,a)*solve(n,m/2,b)*2)%mod;
	return 0;
}

标签:黑色,ARC171E,白色,题解,ll,石头,Tour,移动,我们
From: https://www.cnblogs.com/eastcloud/p/18014180

相关文章

  • 2024牛客寒假算法基础集训营2个人补题题解(K、D)
    比赛链接:2024牛客寒假算法基础集训营2K、TokitsukazeandPassword(easy)题面看着很难实际上只要暴力的东西,赛时看了眼题面就溜了血亏爆搜,枚举\(abcd\)和_可能的值,枚举的情况只有\(9*8*7*6*9=27216\)种。判断按照枚举出的对应值排列出的密码是否满足条件,满足就\(ans++\)写完......
  • Atcoder Educational DP Contest 题解
    比赛链接:Atcoderr或者题单A:Frog1常规线性dp,注意到对于每个落点来说,青蛙只能由第\(i-1\)个石头或者第\(i-2\)个石头转移得到,那么我们让\(dp[i]\)为当跳到第\(i\)个石头上的最小费用。此时显然有:\[dp_i=\min(dp_{i-1}+\left|h_i-h_{i-1}\right|,dp_{i-2}+\left|h_......
  • JOISC 2018 题解
    JOISC2018loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1简单题。根据颜色段均摊的结论,每个点到根的路径上颜色段的总和是\(O(n\logn)\)的,于是直接每次暴力找颜色段即可。复杂度\(O(n\log^2n)\)。提交记录D1T2又是计算几何。我们需要画出一条闭合折线,并且......
  • JOISC 2017 题解
    JOISC2017loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1开场放大。首先,对于一个点,它最后覆盖的一定是一个矩形,这就意味着如果我们知道了\(u,d,l,r\)操作各用了多少次,他们之间的顺序是不重要的,我们可以直接当做把一种操作做完再做剩下的操作,这样就可以做到\(O(......
  • JOISC 2016 题解
    JOISC2016loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1一开始把题目看错了,还写了棵线段树。把询问离线,倒着扫一遍,就变成了求最长不上升子序列,用树状数组维护即可。提交记录D1T2来自Kubic的神仙做法。考虑Filp一个位置和剩下所有位置,记录每个数作为答案......
  • JOISC 2015 题解
    JOISC2015loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1简单题。因为\(k\)很小,考虑依次确定最后第\(i\)位是什么。我们倒序考虑所有操作,维护最后第\(i\)位当前在第几位,就可以一直推下去。提交记录D1T2直接暴力复杂度就是\(O(k4^k)\)的,可以通过。提交......
  • JOISC 2014 题解
    JOISC2014loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1想到了最短路的做法,不过可能还需要整体二分,复杂度至少有2log。有复杂度更优秀的贪心做法。把边按时间倒序加边,然后从终点开始dfs来更新每个点可以的最晚出发时间,每条边走之后肯定就不会再让答案变优了,......
  • CF1628E Groceries in Meteor Town 题解
    题目链接点击打开链接题目解法感觉就是很多个套路组合出来,但我有些套路都不会/ll套路1看到从一点出发,到其他点的路径上的最大权,可以想到\(kruskal\)生成树(这提示我不仅是图可以用\(kruskal\)生成树,树也可以捏)我们建大根的\(kruskal\)生成树,那么将问题转化成了找一个......
  • 图上的游戏 题解
    「2020集训队论文」图上的游戏。算法\(1\):给定点集\(S\),\(|S|=n\),其中有\(m\)个好点。每次可以询问指定点集中是否存在好点,求所有好点。询问次数\(O(\min\{m\logn,n\})\)。对\(S\)分治,若当前不存在好点则退出。每个好点被询问\(\lceil\logn\rceil\)次,分治次......
  • CF1715E Long Way Home题解
    题解注意到\(k\)是一个很小的数,我们考虑分层图是否可做,这时航线有\(n^2\)条,我们可能会建出\((k+1)m+kn^2\)条边,空间会炸掉,然而单单从分层图的角度来优化,是困难的。对于\(m=0\)的情况。考虑\(\text{dp}\),定义\(dp_{i,j}\)表示乘坐不超过\(i\)次航班到达\(j\)的最......