JZOJ 6985 东方永夜抄

少项式 sqrt（

对于一条信息 (si,vi) 令 wsi=vi−A，其余 wi=0。则定义 pi=wifi。

令 F(x) 为答案的 OGF，P(x) 为 {pi} 的 OGF。
有

F(x)=AF2(x)+P(x)F(x)+xAF2(x)+(P(x)−1)F(x)+x=0F(x)=1−P(x)−√(1−P(x))2−4Ax2A

令 Q(x)=(1−P(x))2−4Ax,G(x)=√Q(x)，则显然 G′(x)=12Q′(x)Q−1/2(x)

两边乘 Q(x) 分母有理化得 G′(x)Q(x)=12Q′(x)Q1/2(x)=12Q′(x)G(x)

提取系数得 n∑i=0(i+1)gi+1qn−i=12n∑i=0(i+1)qi+1gn−ign+1=1n+1n+1∑i=1(32i−n−1)qign−i+1

以 f0=0 为基础，得到 pn 再得到 qn，Q(x) 只有 O(k2) 项，暴力 O(nk2) 计算出 gn+1，然后有 fi=−pi+gi2A

不过注意到上面的递推式两边都和 fn+1 相关。此时一个不大高明的做法是把它当做关于 gn+1 的方程解出来。
这样会导致出现额外的分母 2A+wi。

正确的方法是关于 fn+1 去解这个方程，然后再求出 pn+1,gn+1。

不过最终还是会剩下 2A 作为分母。然而 A=0 的情况实际上可以通过平凡地 O(nk) 递推得到结果。
但是 cty 说他没造所以我也没造。

时间复杂度 O(nk2)，求逆所可能产生的 log 是容易避免的。

代码：

#include <cstdio>
#include <algorithm>
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]);
}