「UOJ 269」「清华集训2016」如何优雅地求和

UOJ #269

题意

给定 \(m\) 次函数 \(f\) 和 \(n,a\)，求

\[ \sum_{k = 0}^{n}f(k)\binom{n}{k}a^k(1 - a) ^{n - k} \]

模 \(998244353\)

函数给出 \(0,1,\dotsc,m\) 处的点值

\(1\le n\le 10^9,1\le m\le 2\times 10^4\)

---

做法

把 \(f\) 表示成下降幂的系数形式，令 \(f(x)=\sum\limits_{i=0}^m f_i x^{\underline i}\)

考虑一个下降幂 \(x^{\underline t}\) 的答案

\[ \begin{align} & \sum_{k = 0}^{n} k^{\underline t} \binom{n}{k} a^k(1 - a) ^{n - k} \\ = & \sum_{k=t}^n k^{\underline t} \binom{n-t}{k-t} \frac{n^{\underline t}}{k^{\underline t}} a^k(1 - a) ^{n - k} \\ = & n^{\underline t} \sum_{k=t}^n \binom{n-t}{k-t} a^k (1-a)^{n-k} \\ = & n^{\underline t} \sum_{k=0}^{n-t} \binom{n-t}{k} a^{k+t} (1-a)^{n-k-t} \\ = & n^{\underline t} a^t \sum_{k=0}^{n-t} \binom{n-t}{k} a^k (1-a)^{n-k-t} \\ = & n^{\underline t} a^t \end{align} \]

于是我们只要知道每个系数 \(f_i\) 就可以轻易地计算答案

考虑一个下降幂 \(x^{\underline t}\) 对 \(i\) 处点值的影响 \(i^{\underline t}=\frac{i!}{(i-t)!}\)，写成生成函数的形式

\[ \begin{align} & \sum_{n=0}^\infty \frac{f(n)}{n!}x^n \\ = & \sum_{i=0}^m f_i \sum_{n=i}^\infty \frac{x^n}{(n-i)!} \\ = & \sum_{i=0}^m f_i x^i \sum_{n=0}^\infty \frac{x^n}{n!} \\ = & \left( \sum_{i=0}^m f_i x^i \right) e^x \end{align} \]

于是只需要求出 \(\sum\limits_{n=0}^m \frac{f(n)}{n!} x^n\) 和 \(e^{-x}\) 的卷积就好了

复杂度 \(\mathcal O(m\log m)\)

---

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ull unsigned long long

const unsigned N = 1<<16, P = 998244353;
struct Z{
	unsigned x;
	Z(const unsigned _x=0):x(_x){}
	inline Z operator +(const Z &rhs)const{ return x+rhs.x<P?x+rhs.x:x+rhs.x-P;}
	inline Z operator -(const Z &rhs)const{ return x<rhs.x?x-rhs.x+P:x-rhs.x;}
	inline Z operator -()const{ return x?P-x:0;}
	inline Z operator *(const Z &rhs)const{ return static_cast<ull>(x)*rhs.x%P;}
	inline Z operator +=(const Z &rhs){ return x=x+rhs.x<P?x+rhs.x:x+rhs.x-P, *this;}
	inline Z operator -=(const Z &rhs){ return x=x<rhs.x?x-rhs.x+P:x-rhs.x, *this;}
	inline Z operator *=(const Z &rhs){ return x=static_cast<ull>(x)*rhs.x%P, *this;}
};
int n, m, x;
vector<Z> a, b;
Z ans, w[N];
inline Z Pow(Z x, int y=P-2){
	Z ans=1;
	for(; y; y>>=1, x=x*x) if(y&1) ans=ans*x;
	return ans;
}
inline void Init(int N){
	for(int i=1; i<N; i<<=1){
		w[i]=1;
		Z t=Pow(3, (P-1)/i/2);
		for(int j=1; j<i; ++j) w[i+j]=w[i+j-1]*t;
	}
}
inline int Get(int x){ int n=1; while(n<=x) n<<=1; return n;}
inline void DFT(vector<Z> &f, int n){
	static ull F[N];
	if((int)f.size()!=n) f.resize(n);
	for(int i=0, j=0; i<n; ++i){
		F[i]=f[j].x;
		for(int k=n>>1; (j^=k)<k; k>>=1);
	}
	for(int i=1; i<n; i<<=1) for(int j=0; j<n; j+=i<<1){
		Z *W=w+i;
		ull *F0=F+j, *F1=F+j+i;
		for(int k=j; k<j+i; ++k, ++W, ++F0, ++F1){
			ull t=(*F1)*(W->x)%P;
			(*F1)=*F0+P-t, (*F0)+=t;
		}
	}
	for(int i=0; i<n; ++i) f[i]=F[i]%P;
}
inline void IDFT(vector<Z> &f, int n){
	f.resize(n), reverse(f.begin()+1, f.end());
	DFT(f, n);
	Z I=Pow(n);
	for(int i=0; i<n; ++i) f[i]=f[i]*I;
}
inline vector<Z> operator *(const vector<Z> &f, const vector<Z> &g){
	if(f.size()*g.size()<=1000){
		vector<Z> ans;
		ans.resize(f.size()+g.size()-1);
		for(unsigned i=0; i<f.size(); ++i) for(unsigned j=0; j<g.size(); ++j)
		ans[i+j]+=f[i]*g[j];
		return ans;
	}
	static vector<Z> F, G;
	F=f, G=g;
	int p=Get(f.size()+g.size()-2);
	DFT(F, p), DFT(G, p);
	for(int i=0; i<p; ++i) F[i]*=G[i];
	IDFT(F, p);
	return F.resize(f.size()+g.size()-1), F;
}
int main() {
	scanf("%d%d%d", &n, &m, &x), a.resize(m+1), b.resize(m+1);
	for(int i=0; i<=m; ++i) scanf("%d", &a[i].x);
	b[m]=1;
	for(int i=2; i<=m; ++i) b[m]*=i;
	b[m]=Pow(b[m]);
	for(int i=m; i; --i) b[i-1]=b[i]*i, a[i]*=b[i], b[i]*=(i&1?P-1:1);
	Init(Get(m*2)), a=a*b;
	for(int i=0, k=1; i<=m; k=(ull)k*(n-i++)%P*x%P) ans=ans+a[i]*k;
	return printf("%d", ans), 0;
}