题面

求：\(\sum_{i=0}^{n} f(i)2^{n-i}{n \choose i}\),其中\(f(x)\)是一个\(K\)次多项式,\(n\leq 10^9,K\leq 5000\)

分析

关键在于: \(i^j=\sum_{h=0}^{i}{n \choose i}{j \brace i}\)
证明：考虑意义：
LHS表示将i个不同的球放入j个不同的盒子中的方案数
RHS表示枚举有多少空盒子，用第二类斯特拉林数计算对应的方案数
\( \begin {aligned}\sum_{i=0}^{n} f(i)*2^{n-i}*{n \choose i} &= \sum_{i=0}^{n}\sum_{j=0}^{k}a_ji^j2^{n-i}{n\choose i} \\&=\sum_{j=0}^{k}a_j\sum_{i=0}^{n} i^j{n \choose i}2^{n-i} \\&=\sum_{j=0}^{k} a_j\sum_{i=0}^{n}\sum_{h=0}^{j}{j \brace h}{i \choose h} h! {n\choose i}2^{n-i} \\&=\sum_{j=0}^{k} a_j\sum_{h=0}^{j}{j \brace h}h!\sum_{i=0}^{n}{i \choose h}{n \choose i}2^{n-i} \\ &=\sum_{j=0}^{k} a_j\sum_{h=0}^{j}{j \brace h}h!{n \choose h}\sum_{i=0}^{n}{n-h \choose i-h}2^{n-i} \\&=\sum_{j=0}^{k} a_j\sum_{h=0}^{j}{j \brace h}h!{n \choose h}3^{n-h} \end {aligned} \)

#include<bits/stdc++.h>
#define ll long long
const int p=998244853;
using namespace std;

inline int ksm(ll a,int b) {
	ll ret=1;
	while(b) {
		if(b&1) ret=ret*a%p;
		a=a*a%p,b>>=1;
	}
	return ret;
}
const int N=5005;
int d[N][N],n,K,a[N],s[N];

int main() {
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	scanf("%d%d",&n,&K);
	for(int i=0;i<=K;i++) scanf("%d",&a[i]);
	d[0][0]=1;
	for(int i=1;i<=K;i++) {
		for(int j=1;j<=i;j++) {
			d[j][i]=((ll)d[j][i-1]*j+d[j-1][i-1])%p;
		}
	}
	int jc=1,mi=ksm(3,n),inv3=ksm(3,p-2)%p,c=1;
	s[0]=mi;
	for(int i=1;i<=K;i++) {
		c=(ll)c*(n-i+1)%p*ksm(i,p-2)%p;
		mi=(ll)mi*inv3%p;
		jc=(ll)jc*i%p;
		s[i]=(ll)c*jc%p*mi%p;
	}
	int ans=0;
	for(int i=0;i<=K;i++) {
		ll sum=0;
		for(int j=0;j<=i;j++) {
			sum=(sum+(ll)d[j][i]*s[j])%p;
		}
		ans=((ll)ans+sum*a[i])%p;
	}
	printf("%d\n",ans);
	return 0;
}