洛谷 4705 玩游戏

现在发现新的多项式板子写分治 NTT 真麻烦……

显然 k 次价值的期望是 1nmn∑i=1m∑j=1(ai+bj)k

先别管那个 1nm，考虑剩下的那个部分： n∑i=1m∑j=1(ai+bj)k=n∑i=1m∑j=1k∑e=0(ke)aeibk−ej=n∑i=1m∑j=1k∑e=0k!e!(k−e)!aeibk−ej=k!n∑i=1m∑j=1k∑e=0aeie!bk−ej(k−e)!=k!k∑e=0n∑i=1aeie!m∑j=1bk−ej(k−e)!

于是变成了 k∑e=0xee!n∑i=1aei,k∑e=0xee!n∑i=1bei 的卷积……
考虑如何对于所有 e 求出 n∑i=1aei。

众所周知生成函数是万能的，故可以对于每个 ai 构造生成函数然后加起来。
即 n∑i=1aei=[xe]n∑i=111−aix

注意到如果右边是个 ∏ 就好办了，直接提分母出来分治 NTT 然后求逆就行了。
但是人家是 ∑ 喔！
怎么把 ∑ 变成 ∏ 呢？当然是 ln 辣！
但是直接 ln 似乎依然不可做……

注意到我们实际上是想要 n∏i=1(1−aix)，又注意到如果结合 ln 和求导的话就可以把它放回分母上。
即 [ln(1−aix)]′=−ai1−aix

并且展开来会发现 11−aix=−x[ln(1−aix)]′+1

于是得到 n∑i=111−aix=n−xn∑i=1[ln(1−aix)]′=n−x[lnn∏i=1(1−aix)]′

惊了！居然得到了一个神奇的形式！
于是一遍分治 NTT 一遍多项式 ln 外加求个导就搞定了，最后再做一次卷积。
复杂度 O(nlog2n)（视 n,m,t 均同阶）。

以及我从神鱼那里学来的多项式板子有些操作并不能直接适配分治 NTT……
随着 WA / TLE 的次数增多我总算是调出来了……
（一开始还以为是常数问题来着）

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <algorithm>
#define add(a,b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a,b) (a < b ? a - b + mod : a - b)
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 1 << 18;
const int mod = 998244353;
const int G = 3;
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;
}
struct poly
{
    int a[N + 5];
    inline const int &operator[](int x) const
    {
        return a[x];
    }
    inline int &operator[](int x)
    {
        return a[x];
    }
    inline void clear(int x = 0)
    {
        memset(a + x,0,(N - x + 1) << 2);
    }
} f,g;
int lena,lenb,t,n,lg2[N + 5];
int a[N + 5],b[N + 5];
int rev[N + 5],fac[N + 5],ifac[N + 5],inv[N + 5];
int rt[N + 5],irt[N + 5];
inline void init(int len)
{
    for(n = 1;n < len;n <<= 1);
    for(register int i = 2;i <= n;++i)
        lg2[i] = lg2[i >> 1] + 1;
    int w = fpow(G,(mod - 1) / n);
    rt[n >> 1] = 1;
    for(register int i = (n >> 1) + 1;i <= n;++i)
        rt[i] = (long long)rt[i - 1] * w % mod;
    for(register int i = (n >> 1) - 1;i;--i)
        rt[i] = rt[i << 1];
    fac[0] = 1;
    for(register int i = 1;i <= n;++i)
        fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[n] = fpow(fac[n],mod - 2);
    for(register int i = n;i;--i)
        ifac[i - 1] = (long long)ifac[i] * i % mod;
    for(register int i = 1;i <= n;++i)
        inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
}
inline void ntt(poly &a,int type,int n)
{
    type == -1 && (reverse(a.a + 1,a.a + n),1);
    int lg = lg2[n] - 1;
    for(register int i = 0;i < n;++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg),
        i < rev[i] && (swap(a[i],a[rev[i]]),1);
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
            {
                int t = (long long)rt[m | j] * a[i | j | m] % mod;
                a[i | j | m] = dec(a[i | j],t),a[i | j] = add(a[i | j],t);
            }
    if(type == -1)
        for(register int i = 0;i < n;++i)
            a[i] = (long long)a[i] * inv[n] % mod;
}
inline void mul(poly &a,const poly &b,int n)
{
    static poly x,y;
    int lim = 1;
    for(;lim < (n << 1);lim <<= 1);
    memcpy(x.a,a.a,lim << 2),memcpy(y.a,b.a,lim << 2);
    memset(x.a + n,0,lim - n + 1 << 2),memset(y.a + n,0,lim - n + 1 << 2);
    ntt(x,1,lim),ntt(y,1,lim);
    for(register int i = 0;i < lim;++i)
        x[i] = (long long)x[i] * y[i] % mod;
    ntt(x,-1,lim);
    memcpy(a.a,x.a,lim << 2);
}
inline poly inverse(const poly &f,int n)
{
    static int s[30];
    static poly g,h,q;
    int lim = 1,top = 0;
    g.clear();
    for(;n > 1;s[++top] = n,n = (n + 1) >> 1);
    g[0] = fpow(f[0],mod - 2);
    for(;top;--top)
    {
        n = s[top];
        for(;lim < (n << 1);lim <<= 1);
        q = g,h = f,h.clear(n);
        ntt(g,1,lim),ntt(h,1,lim);
        for(register int i = 0;i < lim;++i)
            g[i] = (long long)g[i] * g[i] % mod * h[i] % mod;
        ntt(g,-1,lim);
        for(register int i = 0;i < n;++i)
            g[i] = dec(add(q[i],q[i]),g[i]);
        g.clear(n);
    }
    return g;
}
inline void derivative(poly &f,int n)
{
    for(register int i = 1;i < n;++i)
        f[i - 1] = (long long)f[i] * i % mod;
    f[n - 1] = 0;
}
inline void integral(poly &f,int n)
{
    for(register int i = n - 1;~i;--i)
        f[i + 1] = (long long)f[i] * inv[i + 1] % mod;
    f[0] = 0;
}
inline poly ln(const poly &f,int n)
{
    static poly g;
    g = f,derivative(g,n),mul(g,inverse(f,n),n),g.clear(n),integral(g,n);
    return g;
}
inline poly exp(const poly &f,int n)
{
    static int s[30];
    static poly g,h;
    int lim = 1,top = 0;
    g.clear();
    for(;n > 1;s[++top] = n,n = (n + 1) >> 1);
    g[0] = 1;
    for(;top;--top)
    {
        n = s[top];
        for(;lim < (n << 1);lim <<= 1);
        h = g,g = ln(g,n);
        for(register int i = 0;i < n;++i)
            g[i] = dec(f[i],g[i]);
        g[0] = add(g[0],1);
        ntt(g,1,lim),ntt(h,1,lim);
        for(register int i = 0;i < lim;++i) 
            g[i] = (long long)g[i] * h[i] % mod;
        ntt(g,-1,lim);
        g.clear(n);
    }
    return g;
}
inline poly power(const poly &f,int k,int n)
{
    static poly g;
    g = ln(f,n);
    for(register int i = 0;i < n;++i)
        g[i] = (long long)g[i] * k % mod;
    g = exp(g,n);
    return g;
}
namespace Mod_sqrt
{
    typedef pair<int,int> cp;
    int w;
    inline cp operator*(const cp &a,const cp &b)
    {
        return cp(((long long)a.first * b.first % mod + (long long)a.second * b.second % mod * w % mod) % mod,((long long)a.first * b.second % mod + (long long)a.second * b.first % mod) % mod);
    }
    inline cp pow(cp a,int b)
    {
        cp ret(1,0);
        for(;b;b >>= 1)
            (b & 1) && (ret = ret * a,1),a = a * a;
        return ret;
    }
    inline int mod_sqrt(int x)
    {
        int y = rand() % mod;
        for(;fpow(w = ((long long)y * y % mod - x + mod) % mod,mod - 1 >> 1) <= 1;y = rand() % mod);
        cp ret = pow(cp(y,1),mod + 1 >> 1);
        return min(ret.first,mod - ret.first);
    }
}
using Mod_sqrt::mod_sqrt;
inline poly sqrt(const poly &f,int n)
{
    static int s[30];
    static poly g,h;
    int top = 0;
    g.clear();
    for(;n > 1;s[++top] = n,n = (n + 1) >> 1);
    g[0] = mod_sqrt(f[0]);
    for(;top;--top)
    {
        n = s[top];
        for(register int i = 0;i < n;++i)
            h[i] = add(g[i],g[i]);
        h = inverse(h,n),mul(g,g,n);
        for(register int i = 0;i < n;++i)
            g[i] = add(g[i],f[i]);
        mul(g,h,n);
    }
    return g;
}
void solve(poly &f,int *g,int l,int r,int L,int R,int len)
{
    if(l == r)
    {
        l < len ? (f[L] = 1,f[R] = mod - g[l]) : (f[L] = 1,f[R] = 0);
        return ;
    }
    int mid = l + r >> 1,MID = L + R >> 1;
    solve(f,g,l,mid,L,MID,len),solve(f,g,mid + 1,r,MID + 1,R,len);
    static poly x,y;
    for(register int i = 0;i <= mid - l + 1;++i)
        x[i] = f[L + i],y[i] = f[MID + 1 + i];
    mul(x,y,mid - l + 2);
    for(register int i = 0;i <= r - l + 1;++i)
        f[L + i] = x[i];
}
int main()
{
    read(lena),read(lenb);
    for(register int i = 0;i < lena;++i)
        read(a[i]);
    for(register int i = 0;i < lenb;++i)
        read(b[i]);
    read(t),init(max(max(lena,lenb) + 1,++t) << 1);
    solve(f,a,0,n / 2 - 1,0,n - 1,lena),solve(g,b,0,n / 2 - 1,0,n - 1,lenb);
    f.clear(++lena),g.clear(++lenb);
    f = ln(f,t),derivative(f,t),g = ln(g,t),derivative(g,t);
    for(register int i = t - 1;i;--i)
        f[i] = mod - f[i - 1];
    f[0] = lena - 1;
    for(register int i = t - 1;i;--i)
        g[i] = mod - g[i - 1];
    g[0] = lenb - 1;
    for(register int i = 0;i < t;++i)
        f[i] = (long long)f[i] * ifac[i] % mod;
    for(register int i = 0;i < t;++i)
        g[i] = (long long)g[i] * ifac[i] % mod;
    mul(f,g,t);
    for(register int i = 1;i < t;++i)
        printf("%d\n",(int)((long long)f[i] * fac[i] % mod * inv[lena - 1] % mod * inv[lenb - 1] % mod));
}