少项式 sqrt（
对于一条信息 \((s_i,v_i)\) 令 \(w_{s_i} = v_i-A\)，其余 \(w_i=0\)。则定义 \(p_i = w_i f_i\)。
令 \(F(x)\) 为答案的 OGF，\(P(x)\) 为 \(\{p_i\}\) 的 OGF。
有
\[ \begin{aligned} F(x) &= AF^2(x) + P(x)F(x) + x \\ AF^2(x)+(P(x)-1)F(x)+x &= 0 \\ F(x) &= \frac{1-P(x)-\sqrt{(1-P(x))^2-4Ax}}{2A} \end{aligned} \]
令 \(Q(x) = (1-P(x))^2 - 4Ax,G(x) = \sqrt{Q(x)}\)，则显然 \[ G'(x) = \frac12Q'(x)Q^{-1/2}(x) \]
两边乘 \(Q(x)\) 分母有理化得 \[
G'(x)Q(x) = \frac12Q'(x)Q^{1/2}(x) = \frac12Q'(x)G(x)
\]
提取系数得 \[ \begin{aligned} \sum\limits_{i=0}^n (i+1)g_{i+1}q_{n-i} &= \frac12 \sum\limits_{i=0}^n (i+1)q_{i+1} g_{n-i} \\ g_{n+1} &= \frac1{n+1}\sum\limits_{i=1}^{n+1}\left(\frac32i-n-1\right) q_i g_{n-i+1} \end{aligned} \]
以 \(f_0=0\) 为基础，得到 \(p_n\) 再得到 \(q_n\)，\(Q(x)\) 只有 \(O(k^2)\) 项，暴力 \(O(nk^2)\) 计算出 \(g_{n+1}\)，然后有 \[ f_i = -\frac{p_i+g_i}{2A} \]
不过注意到上面的递推式两边都和 \(f_{n+1}\) 相关。此时一个不大高明的做法是把它当做关于 \(g_{n+1}\) 的方程解出来。
这样会导致出现额外的分母 \(2A+w_i\)。
正确的方法是关于 \(f_{n+1}\) 去解这个方程，然后再求出 \(p_{n+1},g_{n+1}\)。
不过最终还是会剩下 \(2A\) 作为分母。然而 \(A=0\) 的情况实际上可以通过平凡地 \(O(nk)\) 递推得到结果。
但是 cty 说他没造所以我也没造。
时间复杂度 \(O(nk^2)\)，求逆所可能产生的 \(\log\) 是容易避免的。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
const int N = 1e6;
const int K = 10;
const int CNT = 67;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int n,k,A,Ai;
struct note
{
int s,v;
inline bool operator<(const note &o) const
{
return s < o.s;
}
} a[K + 5];
int inv[N + 5],w[N + 5];
int ind[CNT + 5],cnt;
int f[N + 5],p[N + 5],q[N + 5],g[N + 5];
int main()
{
freopen("night.in","r",stdin),freopen("night.out","w",stdout);
scanf("%d%d%d",&n,&k,&A),inv[1] = 1,Ai = fpow(A,mod - 2);
for(register int i = 2;i <= n;++i)
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
for(register int i = 1;i <= k;++i)
scanf("%d%d",&a[i].s,&a[i].v),
a[i].v = (a[i].v - A + mod) % mod,
w[a[i].s] = a[i].v;
sort(a + 1,a + k + 1);
for(register int i = 0;i <= k;++i)
for(register int j = i;j <= k;++j)
if(a[i].s + a[j].s <= n)
ind[++cnt] = a[i].s + a[j].s;
ind[++cnt] = 1;
sort(ind + 1,ind + cnt + 1),cnt = unique(ind + 1,ind + cnt + 1) - ind - 1;
g[0] = q[0] = 1,q[1] = (4LL * mod - 4LL * A) % mod;
for(register int i = 0;i < n;++i)
{
for(register int j = 2;j <= cnt && ind[j] <= i + 1;++j)
g[i + 1] = (g[i + 1] + (3LL * ind[j] * inv[2] % mod - i - 1 + mod) * q[ind[j]] % mod * g[i - ind[j] + 1]) % mod;
g[i + 1] = (long long)g[i + 1] * inv[i + 1] % mod;
f[i + 1] = (long long)(mod - g[i + 1]) * Ai % mod * inv[2] % mod;
p[i + 1] = (long long)w[i + 1] * f[i + 1] % mod;
g[i + 1] = (long long)(mod - f[i + 1]) * (2LL * A + w[i + 1]) % mod;
if(p[i + 1])
{
p[0] = mod - 1;
for(register int j = 0;j <= k && a[j].s <= i + 1 && i + 1 + a[j].s <= n;++j)
q[i + 1 + a[j].s] = (q[i + 1 + a[j].s] + (i + 1 == a[j].s ? 1LL : 2LL) * p[i + 1] * p[a[j].s]) % mod;
p[0] = 0;
}
}
printf("%d\n",f[n]);
}