题目大意
求
[sum_{i=0}^n f(i){nchoose i} x^i (1-x)^{n-i}
]
模(998244353)
(f)是一个(m)次多项式，以(0)到(m)的点值给出。
(nleq 10^9,mleq 2*10^4,0leq x<998244353)
题解
式子后面长得很像二项式定理，我们要想办法把(f(i))分离出来。
一种高妙的做法是把(f)转成下降幂形式。可能是我做题太少没见过吧
令
[f(x)=sum_{i=0}^m g_i x^{underline{i}}
]
则
[egin{aligned}
ans&=sum_{i=0}^n sum_{j=0}^m g_j i^{underline{j}} {nchoose i} x^i (1-x)^{n-i}\
&=sum_{i=0}^n sum_{j=0}^m g_j n^{underline{j}} {n-j choose n-i} x^i (1-x)^{n-i}\
&=sum_{i=0}^m g_i n^{underline{i}} x^i sum_{j=i}^n {n-i choose n-j} x^{j-i} (1-x)^{n-j}\
&=sum_{i=0}^m g_i n^{underline{i}} x^i\
end{aligned}
]
然后就是要把连续点值的多项式转成下降幂。
[egin{aligned}
f(n)&=sum_{i=0}^m g_i n^{underline{i}}\
frac{f(n)}{n!}&=sum_{i=0}^m g_i frac{1}{(n-i)!}
end{aligned}
]
不妨设(g)从第(m+1)位开始都是(0)，这样长度可以当成(infty)
[egin{aligned}
F&=G*e^x\
G&=F*e^{-x}
end{aligned}
]
(F)和(e^{-x})长度都是(infty)，所以前(m)位卷起来取前(m)位是对的。
这样就可以(O(nlog n))通过这题。
更为通俗的方法
一种不高妙的方法是把(f)二项式反演。
推式子的过程和复杂度都是一样的，但是转成组合数形式就不用那么麻烦了。
其实我写上面那个方法只是想加深对生成函数的理解而已