很牛的题。
题意:很简单了,不再赘述。
做法:
首先需要一个 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\)
-
将 \(p\) 加入栈。
-
弹出栈中除 \(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;
}