题解：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;
}