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

UOJ #269. 【清华集训2016】如何优雅地求和

题意

给定 \(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)\)


代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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;
}
0%