是时候回顾一波青岛站打铁时没想出来的题了QAQ。
题目传送门:ZOJ4069
求由 n 个点组成 k 条链,形成的所有图的方案数,对 1e9+7 取模。
首先,我们先考虑由 m 个点形成 1 条链的不同方案个数。显然对任意排列,去除倒过来的那个就行了。将方案数记为 l_m,则可以得到
l_m = \begin{cases} 1, & m=1 \\ \frac{m!}{2}, & m>1 \end{cases}
那么似乎接下来就是求它的生成函数了。在这里我们选择它的指数型生成函数。
L(x) = \sum_{m=1}^\infty l_m \frac{x^m}{m!} = \frac{1}{2}\left(2x+x^2+x^3+\cdots\right) = x\left(1-\frac{x}{2}\right)\frac{1}{1-x}
那么现在取 k 条链,我们可以计算出
A_k(x) = \sum_{n=1}^\infty a_{n,k} \frac{x^n}{n!} = \left[L(x)\right]^k = x^k \left(1-\frac{x}{2}\right)^k \left(\frac{1}{1-x}\right)^k
由于这 k 条链之间是不考虑先后关系的,所以
b_{n,k} = \frac{a_{n,k}}{k!}
就是最终的答案。
考虑一下题目是多测的,而且测试样例数高达 T = 2 \times 10^4,是不能进行FFT的。
我们可以发现
\left(1-\frac{x}{2}\right)^k = \sum_{s=0}^k C_k^s \left(-\frac{1}{2}\right)^s x^s
是可以用二项式定理做出来的。
然后考虑一下,后面的 1/(1-x)^k 与前面这项进行卷积,其实就相当于对前面的数列进行了 k 次前缀和。
emmmmm,看到网上有个dalao说
求k次前缀和的第m项,想必现在是个人都应该会了
突然自闭.jpg。然后推了推。假设这个数列原来是
\lbrace x_0, x_1, x_2, \cdots \rbrace
对它进行 k+1 次前缀和,它会变成
\lbrace C_k^k x_0, C_{k+1}^k x_0 + C_k^k x_1, C_{k+2}^k x_0 + C_{k+1}^k x_1 + C_k^k x_2, \cdots \rbrace
即第 n 项为
\sum_{i=0}^n C_{k+i}^k x_{n-i}
单次询问复杂度是 O(m) 的,那么现在可以开始写代码啦!
#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;
}
后面的卷积其实不用做前缀和考虑的.
因为(1-k)^{-n}的x^n系数是\binom{n+k-1}{k},这是经典的OGF展开
后面的卷积其实不用做前缀和考虑的.
因为(1-x)^{-k}的x^n系数是\binom{n+k-1}{k},这是经典的OGF展开
(深夜手抖,上一个回复写错了)
是栗巨巨QwQ…我是觉得1/(1-x)是类似于前缀和的意义,然后这样去推系数的(其实是展开忘光了(雾