首页 > 其他分享 >CF128C Games with Rectangle

CF128C Games with Rectangle

时间:2024-01-25 21:23:00浏览次数:29  
标签:矩形 题目 int 四条 Games 条边 CF128C Rectangle 2k

首先来明确一个点,假设我确定了四条竖着的边和四条横着的边:

img

接着如果向通过分别选择横竖不同的边,组成一个满足题目要求的嵌套矩形,那么选择方法一定是唯一的:

img

换句话说,只要我选择了四条边,就一定存在一组(两个)唯一的矩形能够满足题目所述条件

进一步推广,只要选择\(2k\)条边,就能够造出唯一的一组符合题目要求的矩形

那么最后,我们只需要从\(n,m\)条边中分别选出\(2k\)条边进行组合,计算共有多少种不同的情况,也就是\(C^{2k}_n\times C^{2k}_m\)

我使用了递推求\(C_n^m\),也可以直接使用循环枚举(应该不会超时)

这里再解释一下递推式\(C_n^m=C_{n-1}^{m-1}+C^{m}_{n-1}\)

前半部分\(C_{n-1}^{m-1}\)计算的是如果当前第\(n\)个数选中,那么共有这么多种方式,后半部分\(C^{m}_{n-1}\)则是如果不选第\(n\)个数,有多少种情况,求和则是最终\(C^m_n\)的结果了

代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int c[1010][1010];
int n,m,k;
signed main()
{
	cin>>n>>m>>k;
	if(2*k>n || 2*k>m)
	{
		cout<<0;
		return 0;
	}
	for(int i=1;i<=max(n,m);i++) c[i][0]=1;
	for(int i=1;i<=max(n,m);i++) c[i][max(n,m)]=1;
	for(int i=1;i<=max(n,m);i++)
	{
		for(int j=1;j<=max(n,m);j++)
		{
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			c[i][j]%=mod;
		}
	}
	cout<<c[n][2*k]*c[m][2*k]%mod;
}

标签:矩形,题目,int,四条,Games,条边,CF128C,Rectangle,2k
From: https://www.cnblogs.com/lyk2010/p/17988198

相关文章

  • 【Qt之Quick模块】7. Quick基础、常用组件Item、Rectangle、Text、TextInput、TextEdi
    1.概述QtQuick模块是编写QML应用程序的标准库。QtQML模块提供QML引擎和语言基础结构,QtQuick模块提供用QML创建用户界面所需的所有基本类型。它提供了一个可视化画布,包括用于创建和动画化可视化组件、接收用户输入、创建数据模型和视图以及延迟对象实例化的类型。QtQuick模块......
  • 初中英语优秀范文100篇-042Is It Good for Students to Play Video Games?学生玩游戏
    PDF格式公众号回复关键字:SHCZFW042记忆树1Videogameshavebecomemoreandmorepopularnow.翻译现在视频游戏变得越来越流行。简化记忆流行句子结构1主语(Subject):"Videogames"(电子游戏)是句子的主题,表示现在完成时态的承受者。2谓语(Predicate):"havebe......
  • games101-2 透视深度插值矫正与抗锯齿分析
    透视深度插值矫正与抗锯齿分析深度插值的差错原因透视深度插值公式推导games101中的错误msaa与ssaa简要定义games101中ssaa的实现games101中msaa的实现深度插值的差错原因当投影的图形与投影的平面不平行时,这时进行透视投影,从上图中可以看出,投影平面上的线段时均匀......
  • EC-Final 2022 Rectangles
    有点营养的题。很容易做三条竖线,接下来考虑两竖一横。直接枚举横线会变成支持加入区间删除区间维护有多少种方案选择两个点使得任何区间至少包含其一。当然一个想法是线段树分治,以一只log的代价转化为只有加入,这个先放着。胡乱离散化一下,又可以转化为点带权但值域只有\(2n\)。......
  • SPOJ1805 HISTOGRA - Largest Rectangle in a Histogram 题解
    LinkSPOJ1805HISTOGRA-LargestRectangleinaHistogramQuestion在一条水平线上有\(n\)个高为\(a_i\)的矩形,求包含于这些矩形的最大子矩形面积。Solution我们定义\(L_i\)表示有\(a_i\)这个高度的一根悬线,往左最多能平移到什么位置初始化显然,\(a_i=i\)考虑转移......
  • 2D物理引擎 Box2D for javascript Games 第七章 子弹和感应器
    2D物理引擎Box2DforjavascriptGames第七章子弹和感应器你知道Box2D可以在每一个时间步中管理刚体间的碰撞并决算它们。总之,在愤怒的小鸟中制作攻城机器期间,发生了一些错误你可能需要注意一下,有时抛射物会穿过城堡,忽略了碰撞。这里发生了什么?通常,Javascript游戏运行......
  • Steam糖果派对新作《鼠托邦》BBGAMES建设老鼠王国的战略模拟电子游戏
    游戏《鼠托邦Ratopia》由独.立游戏开发团队CasselGames精心打造,将在11月6日起BBIN游戏抢先体验测试。在这款游戏中,您将化身为糖果派对游戏中的老鼠女王,领您的老鼠民众建设城市、勘探地.下领域以扩展生存空间。同时,您有机会根据不同老鼠市民的性格和技能,智慧地分配工作,依靠整......
  • 解决self.draw.draw_rectangle(xy, fill, 1) ValueError: y1 must be greater tha
    我尝试了很多方法,包括单不限于改labelme文件的直接报错,修改pillow包的原文件尝试注释掉raise的地方。最后都以失败告终。还有尝试重新安装最新版的包,来解决。最后经过多次尝试后发现,发生错误的地方的文件是有问题的,至于是什么问题到现在也不知道,那就删除最后停止位置时......
  • CF1854E Games Bundles 题解
    乱搞题设个\(dp[i]\)表示和为\(i\)的子序列个数,那么转移是容易的,\(dp[j]+=dp[j-i]\),然后就判下\(dp[60]+dp[60-i]\)是否大于\(m\),发现这样子搞对于比较大的数可能达不到\(m\)的限制,因为这样子转移,默认的是一个数只选一次,但是我们可以重复选,这启发我们需要设定一个值......
  • 2D物理引擎 Box2D for javascript Games 第五章 碰撞处理
    2D物理引擎Box2DforjavascriptGames第五章碰撞处理碰撞处理考虑到Box2D世界和在世界中移动的刚体之间迟早会发生碰撞。而物理游戏的大多数功能则依赖于碰撞。在愤怒的小鸟中,小鸟摧毁小猪的城堡时,便是依赖碰撞而实现的;在图腾破坏者中,当神像坠落到图腾上或摔碎在地面上......