AT2642 [ARC076A] Reconciled? 题解
2024-10-19 13:40:20
Content
有 \(n\) 只狗和 \(m\) 只猴,现在要把这 \(n+m\) 只动物排成一排,要求相邻两只动物不能同时是狗或者同时是猴。求排列方案总数对 \(10^9+7\) 取模后的值。
数据范围:\(1\leqslant n,m\leqslant 10^5\)。
Solution
首先不难想到,如果 \(|n-m|>1\),那么必然没有方案能够满足要求。
否则,如果 \(n=m\),那么要么是 狗猴狗猴……
这种排列,要么是 猴狗猴狗……
这种排列,又由于每种动物的排列总数都是 \(n!\),因此依据乘法原理可知答案就是 \(2(n!)^2\)。
否则就是 \(|n-m|=1\) 的情况了,我们不妨先放数量少的动物,这样会形成 \(\min\{n,m\}+1\) 个空位,然后直接把剩下那种动物随便放进去每个空位即可。依据乘法原理可知答案就是 \(n!\times m!\)。
那么这道题目就写完了。
Code
namespace Solution {
#define int ll
const int mod = 1e9 + 7, N = 1e5 + 7;
int a, b, fac[N];
iv Main() {
read(a, b), fac[0] = 1;
F(int, i, 1, max(a, b)) fac[i] = fac[i - 1] * i % mod;
if(abs(a - b) > 1) return write(0);
if(a == b) write(2ll * fac[a] % mod * fac[a] % mod);
else write(fac[b] * fac[a] % mod);
return;
}
#undef int
}
最新文章
- Codeforces Round #234A
- Python 对目录中的文件进行批量转码(GBK>;UTF8)
- 获取图片工具类:BitmapUtil
- 如何利用word2013写图文并茂的博客
- 【SQL】靠谱的TRIM函数,附赠过程一枚
- SQL Server常用语句
- atitit.提升开发效率---MDA 软件开发方式的革命(5)----列表查询建模
- ActiveMQ 使用
- ggplot绘图学习笔记
- 初级node+express建站
- IIS提示Server Application Unavailable
- 多目标遗传算法 ------ NSGA-II (部分源码解析) 快速排序代码 sort.c
- 解决ssm项目表单数据提交到数据库乱码问题
- django 缓存信号等
- 使用nodejs去做一个验证码
- SQL语句——重复记录
- webpack导入css及各项loader
- Java Swing 简单介绍
- JMeter学习(二十一)关联(转载)
- zsh: command not found: pip 解决方法