CF1731F Function Sum

题目大意

对于一个长度为nnn的序列aaa。

定义lil_ili​表示iii左边比aia_iai​小的数的个数，即li=∑j=1i−1[aj

定义rir_iri​表示iii右边比aia_iai​大的数的个数，即ri=∑j=i+1n[aj>ai]r_i=\sum\limits_{j=i+1}^{n}[a_j>a_i]ri​=j=i+1∑n​[aj​>ai​]

我们称一个位置是好的，当且仅当li

对于序列aaa，定义函数f(a)=∑i=1nai[aiisgood]f(a)=\sum\limits_{i=1}^na_i[a_i \ is \ good]f(a)=i=1∑n​ai​[ai​ is good]。

现在给定两个整数n,kn,kn,k，请你求出对于所有长度为nnn且1≤ai≤k1\leq a_i\leq k1≤ai​≤k的数列aaa的f(a)f(a)f(a)的和是多少。

题解

设fi,jf_{i,j}fi,j​表示第iii个数为jjj时该位置对答案的贡献。枚举在iii之前小于aia_iai​的数的个数xxx和在iii之后小于aia_iai​的数的个数yyy，那么

fi,j=j×∑x=1i−1Ci−1x×(j−1)x(k−j+1)i−1−x∑y=x+1n−iCn−iy(k−j)yjn−i−yf_{i,j}=j\times \sum\limits_{x=1}^{i-1}C_{i-1}^x\times (j-1)^x(k-j+1)^{i-1-x}\sum\limits_{y=x+1}^{n-i}C_{n-i}^y(k-j)^yj^{n-i-y}fi,j​=j×x=1∑i−1​Ci−1x​×(j−1)x(k−j+1)i−1−xy=x+1∑n−i​Cn−iy​(k−j)yjn−i−y

那么答案就是∑i=1n∑j=1kfi,j\sum\limits_{i=1}^n\sum\limits_{j=1}^{k}f_{i,j}i=1∑n​j=1∑k​fi,j​。

但这样的时间复杂度实在太大，所以我们考虑优化。

观察上面fi,jf_{i,j}fi,j​的表达式，将其视作关于jjj的一个多项式，我们发现这个多项式的最高次数为nnn。

设Fj=∑i=1nfi,jF_j=\sum\limits_{i=1}^nf_{i,j}Fj​=i=1∑n​fi,j​，Gi=∑j=1iFjG_i=\sum\limits_{j=1}^iF_jGi​=j=1∑i​Fj​。那么答案为GkG_{k}Gk​。

因为fi,jf_{i,j}fi,j​中jjj的最高次项的次数为nnn，所以GiG_iGi​中iii的最高次项为n+1n+1n+1。我们可以用拉格朗日插值法求出n+2n+2n+2个GGG的值，就能求出G(k)G(k)G(k)的值了。

时间复杂度为O(n4log⁡n)O(n^4\log n)O(n4logn)。

code

#include
using namespace std;
const int N=55;
long long jc[105],ny[105],f[105];
long long mod=998244353;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
void init(){jc[0]=1;for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;ny[N]=mi(jc[N],mod-2);for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
long long dd(long long n,long long k){long long re=0;for(int i=1;i<=n;i++){long long p=f[i],q=1;for(int j=1;j<=n;j++){if(i!=j){p=p*(k-j)%mod;q=q*(i-j+mod)%mod;}}re=(re+p*mi(q,mod-2)%mod)%mod;}return re;
}
int main()
{long long n,k;init();scanf("%lld%lld",&n,&k);for(int t=1;t<=min(n+2,k);t++){for(int i=1;i<=n;i++){for(int x=0;x<=i-1;x++){for(int y=x+1;y<=n-i;y++){f[t]=(f[t]+C(i-1,x)*mi(t-1,x)%mod*mi(k-t+1,i-1-x)%mod*C(n-i,y)%mod*mi(k-t,y)%mod*mi(t,n-i-y)%mod)%mod;}}}f[t]=t*f[t]%mod;}for(int i=1;i<=n+2;i++) f[i]=(f[i]+f[i-1])%mod;if(k<=n+2) printf("%lld",f[k]);else printf("%lld",dd(n+2,k));return 0;
}