当前位置: 首页 > news >正文

题解:AT_agc065_d [AGC065D] Not Intersect

很牛的题。

题意:很简单了,不再赘述。

做法:

首先需要一个 Raney 引理:对于整数序列 \(a\),若 \(\sum a = 1\),则有且仅有一个 \(a\) 的循环位移满足前缀和均大于 \(0\)

来简单证明一下,首先不会有两个及以上很好说明,因为如果有两个位置开始的循环位移都合法,不妨假设分别为 \(1,p\),那么 \([1,p-1]\) 内的和大于 \(0\)\([p,n]\) 内的和也大于 \(0\),因为是整数,加起来至少是 \(2\),和序列和为 \(1\) 矛盾了。

接下来直接构造一下,如果从 \(1\) 开头合法那么即证,否则找到目前序列 \(a\) 中前缀和最小且最靠后的位置 \(p\),那么 \(p+1\) 开始的位置就一定合法。直观地感受就是我把整个图像向上平移了最小值加一这么多,肯定都是 \(>0\) 的。

一个推论是这个序列 \(n\) 个循环位移两两不同,比较好证,在此略去。


然后是本题做法,我们先对于相邻点的边直接枚举连了多少条,因为这些边没什么限制,然后考虑分配剩余的。

先破环成链,那么因为这里是很多个区间,所以我们不妨从左往右对于每个端点依次考虑选的区间。我们发现,对于一种连边方式,我们可以这么描述:

栈中有元素 \(1\),从左往右扫 \(p=2,3,\cdots n\)

  1. \(p\) 加入栈。

  2. 弹出栈中除 \(p\)\(k\) 个元素,并对栈顶连一条边,不能把栈弹出 \(1\)

可以发现这样是可以覆盖所有的情况的。

这里我们同时钦定最后一定有一条 \(n\rightarrow 1\),实际上这条边是在相邻点的边考虑的但是我们钦定一下,这样的好处在于,如果我们视第一种操作为 \(+1\), 第二种操作视为 \(-k\),那么最终操作之和为 \(1\),是一个定值就非常好操作。

发现我们上面提到了 Raney 定理及其一个推论,所以我们原本是要计数合法的序列,因为有的可能前缀和 \(<0\) 就无法构造,但是现在如果假设序列长度为 \(l\),我们可以把他的权值赋值为 \(\frac1l\),这样加起来刚好还是一样的,就不需要管是否合法了。

考虑我们现在选了 \(i\) 条,那么因为我们钦定了有 \(n\rightarrow 1\) 的边,所以我们需要在上面的序列统计中塞进去 \(m-i+1\) 个负数,还有 \(n-1\)\(+1\),这里可以看出,\(m-i+1 < n-1\) 也就是 \(m<2n-2\),如果大于等于那就无解,直接输出 \(0\)

先考虑负数内部,就等于我有 \(n-2\)\(-1\) 可以分配给这些负数每个数至少一个,方案数 \(\binom{n-3}{m-i}\)

然后考虑正数负数一起排,方案数 \(\binom{n-2+m-i+1}{n-2}\)

然后再考虑一个序列的权值,为 \(\frac{1}{n-2+m-i+1}\)

再考虑,我一开始需要选出来 \(i\) 条相邻的边,为 \(\binom{n}{i}\)

枚举 \(i\),将上面的全部乘起来即可。

注意对于 \(n\le 2\) 的情况比较神秘,直接特判即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e7 + 5, mod = 1e9 + 7;
int n, m, jc[maxn], revjc[maxn], inv[maxn], lim;
void prepare() {jc[0] = revjc[0] = revjc[1] = 1;for (int i = 1; i <= 2 * n; i++)jc[i] = jc[i - 1] * i % mod;inv[0] = inv[1] = 1;for (int i = 2; i <= 2 * n; i++)revjc[i] = (mod - mod / i) * revjc[mod % i] % mod, inv[i] = revjc[i];for (int i = 2; i <= 2 * n; i++)revjc[i] = revjc[i - 1] * revjc[i] % mod;
}
int C(int m, int n) {if(m > lim || n > lim)return 0;if(m < 0 || n < 0 || m < n)return 0;return jc[m] * revjc[n] % mod * revjc[m - n] % mod;
}
signed main() {cin >> n >> m;if(n <= 2) {cout << (m <= n - 1) << endl;return 0;}lim = 2 * n - 3;if(m > 2 * n - 3) {cout << 0 << endl;return 0;}prepare();int ans = 0;for (int i = 0; i <= min(n, m); i++) {int k = m - i + 1;if(n - 1 + k > lim)continue;ans = (ans + inv[n - 1 + k] * C(n, i) % mod * C(n - 3, k - 1) % mod * C(n - 1 + k, k)) % mod;//	cout << C(n, i) << " " << inv[n - 1 + k] << endl;}cout << ans << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=26706

相关文章:

  • uniapp滚动导航 - unique
  • 滚动导航 - unique
  • windows剪切板工具
  • P1545 [USACO04DEC] Dividing the Path G 题解
  • 视频采集程序
  • java作业2
  • 关于PPT的课后作业
  • RK 系列 GPU 驱动检查方法
  • 咕乡
  • Linux随记(十八) - 详解
  • week2课后作业
  • Java 语言程序设计(第二讲 方法)动手动脑与课后实验问题整理文档 - 20243867孙堃2405
  • 算法第一章
  • mac打开app提示文件损坏解决方案
  • QBXT2025S刷题 Day7题
  • 无需重新训练即可更新语音识别词汇
  • 深入解析:vscode中无法使用npm node
  • 第一次算法作业
  • AI元人文:新的评价与启示
  • Ai元人文:岐金兰回应
  • Why is English commonly used in scientific literature?
  • 第二次课程
  • 考研系列—操作系统:冲刺笔记(1-3章) - 指南
  • 智能照明系统厂家最新推荐榜:智慧光控与节能方案口碑之选
  • 2025工业网线优质厂家最新推荐榜:品质卓越与技术领先之选
  • 上海殡葬一条龙服务最新推荐:专业关怀与人性化服务口碑之选
  • 中空扳手实力厂家最新推荐榜:专业制造与耐用品质深度解析
  • 驾驭“人造太阳”:用 AI 来解锁聚变核能
  • sg.Multiline 和 sg.Output 有什么区别?怎么看起来一样?
  • 中科微GNSS卫星定位产品