UOJ269【清华集训2016】如何优雅地求和【数论，多项式】

题目描述：求

$$\sum_{k=0}^nf(k)\binom{n}{k}x^k(1-x)^{n-k}$$

输入$n$，$f(x)$的次数上界$m$，$x$，$f(0,1,\ldots,m)$，对$998244353$取模。

数据范围：$1\leq n\leq 10^9,1\leq m\leq 2*10^4,0\leq a_i,x<998244353$

现在来讲正解：首先我们把$f(x)$用下降幂来表示，（看到这里的快点关掉，然后自己推一推）

$$\begin{align*}Ans&=\sum_{k=0}^n\sum_{i=0}^ma_i*\frac{k!}{(k-i)!}\frac{n!}{k!(n-k)!}x^k(1-x)^{n-k} \\&=\sum_{k=0}^n\sum_{i=0}^ma_i*\frac{n!}{(k-i)!(n-k)!}x^k(1-x)^{n-k} \\&=\sum_{i=0}^ma_in!\sum_{k=i}^n\frac{x^k}{(k-i)!}*\frac{(1-x)^{n-k}}{(n-k)!} \\&=\sum_{i=0}^ma_ix^in!(e^x*e^{1-x}[x^{n-i}]) \\&=\sum_{i=0}^ma_ix^i\frac{n!}{(n-i)!}\end{align*}$$

然后就是考虑如何点值转下降幂了

$$\begin{align*}f(i)&=\sum_{j=0}^ma_j\frac{i!}{(i-j)!} \\\frac{f(i)}{i!}&=\sum_{j=0}^ma_j*\frac{1}{(i-j)!}\end{align*}$$

所以$f(i)$的EGF等于$a$的OGF乘上$e^x$，所以$a$的OGF等于$f(i)$的EGF乘上$e^{-x}$，使用NTT优化计算，时间复杂度$O(m\log m)$

 #include<bits/stdc++.h>

 #define Rint register int

 using namespace std;

 typedef long long LL;

 const int N =  << , mod = , G = , Gi = ;

 int n, m, x, A[N], B[N], fac[N], invfac[N], ans;

 inline int kasumi(int a, int b){

     int res = ;

     while(b){

         if(b & ) res = (LL) res * a % mod;

         a = (LL) a * a % mod;

         b >>= ;

     }

     return res;

 }

 inline void init(){

     fac[] = ;

     for(Rint i = ;i <= m;i ++) fac[i] = (LL) i * fac[i - ] % mod;

     invfac[m] = kasumi(fac[m], mod - );

     for(Rint i = m;i;i --) invfac[i - ] = (LL) i * invfac[i] % mod;

 }

 int rev[N];

 inline int calrev(int len){

     int limit = , L = -;

     while(limit <= len){limit <<= ; L ++;}

     for(Rint i = ;i < limit;i ++)

         rev[i] = (rev[i >> ] >> ) | ((i & ) << L);

     return limit;

 }

 inline void NTT(int *A, int limit, int type){

     for(Rint i = ;i < limit;i ++)

         if(i < rev[i]) swap(A[i], A[rev[i]]);

     for(Rint mid = ;mid < limit;mid <<= ){

         int Wn = kasumi(type ==  ? G : Gi, (mod - ) / (mid << ));

         for(Rint j = ;j < limit;j += (mid << )){

             int w = ;

             for(Rint k = ;k < mid;k ++, w = (LL) w * Wn % mod){

                 int x = A[j + k], y = (LL) w * A[j + k + mid] % mod;

                 A[j + k] = (x + y) % mod;

                 A[j + k + mid] = (x - y + mod) % mod;

             }

         }

     }

     if(type == -){

         int inv = kasumi(limit, mod - );

         for(Rint i = ;i < limit;i ++)

             A[i] = (LL) A[i] * inv % mod;

     }

 }

 int main(){

     scanf("%d%d%d", &n, &m, &x);

     init();

     for(Rint i = ;i <= m;i ++){

         scanf("%d", A + i);

         A[i] = (LL) A[i] * invfac[i] % mod;

         B[i] = invfac[i];

         if(i & ) B[i] = mod - B[i];

     }

     int limit = calrev(m << );

     NTT(A, limit, ); NTT(B, limit, );

     for(Rint i = ;i < limit;i ++) A[i] = (LL) A[i] * B[i] % mod;

     NTT(A, limit, -);

     int w = ;

     for(Rint i = ;i <= m;i ++){

         ans = (ans + (LL) w * A[i] % mod) % mod;

         w = (LL) w * (mod + n - i) % mod * x % mod;

     }

     printf("%d", ans);

 }

UOJ269

启发：推柿子遇到多项式时应考虑多项式的各种形式，如点值，普通/上升/下降幂等。

巴特西

UOJ269【清华集训2016】如何优雅地求和【数论，多项式】

最新文章

热门文章