Feb 14, 2019 由 小羊
是时候回顾一波青岛站打铁时没想出来的题了QAQ。
题目传送门:ZOJ4069
求由 个点组成 条链,形成的所有图的方案数,对 1e9+7 取模。
首先,我们先考虑由 个点形成 条链的不同方案个数。显然对任意排列,去除倒过来的那个就行了。将方案数记为 ,则可以得到
那么似乎接下来就是求它的生成函数了。在这里我们选择它的指数型生成函数。
那么现在取 条链,我们可以计算出
由于这 条链之间是不考虑先后关系的,所以
就是最终的答案。
考虑一下题目是多测的,而且测试样例数高达 ,是不能进行FFT的。
我们可以发现
是可以用二项式定理做出来的。
然后考虑一下,后面的 与前面这项进行卷积,其实就相当于对前面的数列进行了 次前缀和。
emmmmm,看到网上有个dalao说
求k次前缀和的第m项,想必现在是个人都应该会了
突然自闭.jpg。然后推了推。假设这个数列原来是
对它进行 次前缀和,它会变成
即第 项为
单次询问复杂度是 的,那么现在可以开始写代码啦!
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
lld fac[MAXN], inv[MAXN], invs[MAXN];
inline void init()
{
fac[0] = invs[0] = 1;
fac[1] = inv[1] = invs[1] = 1;
for (int i = 2; i < MAXN; i++)
{
fac[i] = i * fac[i-1] % MOD;
inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
invs[i] = inv[i] * invs[i-1] % MOD;
}
}
inline lld C(int n, int k)
{
if (n < k) return 0;
return fac[n] * invs[k] % MOD * invs[n-k] % MOD;
}
void solve()
{
int n, m, k;
scanf("%d %d", &n, &m);
if (m > n)
{
printf("0\n");
}
else if (m == n)
{
printf("%lld\n", fac[n-1]*inv[2]%MOD);
}
else
{
k = n - m;
lld ans = 0, inv2s = 1;
for (int i = m; i >= 0; i--)
{
ans += C(k-1+i,i) * C(k, m-i) % MOD * inv2s % MOD;
inv2s = inv2s * (MOD-inv[2]) % MOD;
}
ans = (ans % MOD + MOD) % MOD;
ans = ans * fac[n] % MOD * invs[k] % MOD;
printf("%lld\n", ans);
}
}
int main()
{
init();
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}