2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数)

这篇具有很好参考价值的文章主要介绍了2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

t(t<=1e6)组样例,每次给定一个n(n<=1e9),统计边长为n的上述三角形的等边三角形个数

其中等边三角形的三个顶点,可以在所有黑色三角形&白色三角形的顶点中任取,

答案对1e9+7取模

思路来源

申老师 & oeis A000332

Solution to Problem #3

题解

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

oeis打一下前四项的表,发现是C(n,4),并且还有说明,

是等于长度为n时的等边三角形,任取顶点时,不限边长大小的等边三角形个数

看了一下证明,感觉也是变相计数,这里提供一种计数方式,可能赛中还是会选择打表吧

计数方式

对于边长为n的三角形,三个点都在三角形的三条边上的方案,恰有n种

图示分别对应n=2,3,4的情形,

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

所以,可以枚举每个边长i,统计边长=i的正向的三角形的个数,每个的贡献是i

因为倒立的边长为i的三角形,会在正向为2*i的三角形中被枚举到,所以忽略

归纳/找规律可发现,边长为n-i+1的正向三角形的出现次数是i*(i+1)/2,有下式成立:

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数),组合数学(容斥原理),组合数学,计数,找规律

恒等式的组合意义

从n+3个数选4个数时,可以枚举第三个数的位置,左边i+1个位置选2个,右边选1个

但是确实没有看出来其与三角形选择方法的关联关系

代码

输出C(n+3,4)即可,即(n+3)*(n+2)*(n+1)*n/24文章来源地址https://www.toymoban.com/news/detail-725032.html

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pb push_back
#define all(a) a.begin(),a.end()
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
const int mod=1e9+7,inv2=(mod+1)/2,inv6=(mod+1)/6;
int t,n;
int sol(int x){
	int a=1ll*(n+3)*(n+2)%mod*inv6%mod;
	int b=1ll*(n+1)*n%mod*inv2%mod*inv2%mod;
	return 1ll*a*b%mod;
}
int main(){
	sci(t);
	while(t--){
		sci(n);
		printf("%d\n",sol(n));
	}
	return 0;
}

到了这里,关于2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 黑白棋(Othello, ACM/ICPC World Finals 1992, UVa220)rust解法

    你的任务是模拟黑白棋游戏的进程。黑白棋的规则为:黑白双方轮流放棋子,每次必须让新放的棋子“夹住”至少一枚对方棋子,然后把所有被新放棋子“夹住”的对方棋子替换成己方棋子。一段连续(横、竖或者斜向)的同色棋子被“夹住”的条件是两端都是对方棋子(不

    2024年02月08日
    浏览(33)
  • DNA序列(DNA Consensus String, ACM/ICPC Seoul 2006, UVa1368) rust解法

    输入m个长度均为n的DNA序列,求一个DNA序列,到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数,例如,ACGT和GCGA的Hamming距离为2(左数第1, 4个字符不同)。 输入整数m和n(4≤m≤50,4≤n≤1000),以及m个长度为n的DNA序列(只包含字母A,C,

    2024年02月07日
    浏览(38)
  • Win7 Server 漏洞修复(CVE-2017-**、CVE-2018-**、CVE-2019-**、CVE-2012-**)

    Windows 7 Server 服务器也被漏洞扫描找出来几个漏洞,如下: 端口 协议 服务 漏洞 解决方案 445 TCP microsoft-ds Microsoft Windows SMB 远程代码执行漏洞(CVE-2017-0143)(MS17-010)【原理扫描】``Microsoft Windows SMB 远程代码执行漏洞(CVE-2017-0144)(MS17-010)【原理扫描】``Microsoft Windows SMB 远程代码执行

    2024年02月05日
    浏览(71)
  • BUUCTF Misc [SUCTF2018]single dog & 我吃三明治 & sqltest & [SWPU2019]你有没有好好看网课?

    目录 [SUCTF2018]single dog 我吃三明治 sqltest [SWPU2019]你有没有好好看网课? 下载文件 使用kali的binwalk工具分析 进行文件分离 解压其中的压缩包,得到1.txt 看内容应该是js加密后的结果,复制到AAEncode在线解密网站 得到flag             flag{happy double eleven}  下载文件 使用010 eitor打

    2023年04月08日
    浏览(45)
  • 超百万人用它生成3D头像,这项技术刚刚中选了SIGGRAPH Asia 2022

    如何才能做一个和真人一样的 3D 头像? 先上传一张照片:   变成这样:   换一个人的照片:     再看一个例子:   眼镜也可以放进来:       在此基础上,还可以换上各种各样的发型、饰品,眼睛、帽子、发色、胡须,皆可编辑。         这效果,是不是可以做一套自

    2023年04月09日
    浏览(47)
  • Ubuntu 22.04.2 LTS 安装搜狗输入法后,修改区域格式Regional Format crash 崩溃 ,改用bash 指令修改

    系统已经升级到最新  基于Ubuntu 20.04 LTS apt upgrade升级而来。 gnome-language-selector 最终设置的是locale各参数  命令行设置为中文 Region Language 选择中文 重启   实际已经成功,但是图形界面显示有错误。不管了。      

    2024年02月12日
    浏览(58)
  • 2020ICPC南京站

    K Co-prime Permutation 题意:给定n和k,让你构造n的排列,满足gcd(pi, i)=1的个数为k。 思路:因为x和x-1互质,1和任何数互质,任何数和它本身不互质 当k为奇数时,p1=1,后面k-1个数两两互换 当k为偶数时,后面k个数两两互换 Let\\\'s Play Curling 题意:给定n块红色石头,m块蓝色石头的位

    2024年02月10日
    浏览(40)
  • 2023ICPC西安邀请赛

    更好的阅读体验:传送门 比赛完由于被旅游、赶ddl、上班等等各种事情影响,导致我现在才有时间可以写写小作文,这中间隔得时间有点长了,已经不知道从哪开始说起了,灵感也都流失了… 比赛前一个周,我的队友djk,也是我的舍友,周一从合肥回来,嗓子的声音严重变

    2024年02月05日
    浏览(44)
  • 2020ICPC南京【个人题解EFHKLM】

    首先如果炸弹在(0,0)或者机器人最终停在炸弹处,那么一定Impossible。 对于其他的情况,如果存在一条路径使得机器人可以不经过炸弹,那么一定存在一种方案,使得相同的方向在这个方案种是连在一起的。 于是可以直接枚举所有方向的排列,共4!个,判断每一种排列能否绕过

    2023年04月09日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包