来一道简单数论。
求 \(\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^x\) ，其中 \(1\le x\le k\)
\(n\le 2e5,k\le 300\)
显然是一个 \(O(nk)\) 的做法
我们来推式子
\[\begin{aligned}
\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^x&=\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}\sum\limits_{i=0}^xC_{x}^ia_l^ia_r^{x-i}
\\
&=\sum\limits_{i=0}^xC_{x}^i\sum\limits_{l=1}^{n-1}(a_l^i)\sum\limits_{r=l+1}^{n}(a_r^{x-i})
\end{aligned}\]
左边中间的式子都可以直接处理出来，但是右边的却难以处理，因为他和 \(l\) 有关，有什么办法呢。
考虑容斥。
\[\begin{aligned}
\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^x&=\frac {\sum\limits_{l=1}^{n-1}\sum\limits_{r=1}^{n}(a_l+a_r)^x-\sum\limits_{i=1}^n(2a_i)^x}2
\end{aligned}\]
也就是说我们再来推 \(\sum\limits_{l=1}^{n-1}\sum\limits_{r=1}^{n}(a_l+a_r)^x\) 这个式子。
可以得到
\(\sum\limits_{i=0}^xC_{x}^i\sum\limits_{l=1}^{n-1}(a_l^i)\sum\limits_{r=1}^{n}(a_r^{x-i})\)
然后都可以通过预处理得到
时间复杂度 \(O(nk)\)
启发：
对于一些求和式，有时候可以改变求和式的位置，说不定更容易分析题目。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=2e5+10,MODD=998244353;
int n,k;
int a[MAXN],sum[MAXN][310];
LL ans[MAXN],C[310][310];
void init() {
C[0][0]=1;
for(int i=1;i<=300;++i) {
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j) {
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MODD;
}
}
}
LL ksm(LL x,LL y) {
LL ret=1;
while(y) {
if(y&1) ret=ret*x%MODD;
x=x*x%MODD;
y>>=1;
}
return ret;
}
int main () {
init();
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i) {
int ls=1;
for(int j=0;j<=k;++j) {
sum[i][j]=(sum[i-1][j]+ls)%MODD;
ls=((LL)ls*a[i])%MODD;
}
}
for(int i=1;i<=n;++i) {
LL pp=1;
for(int j=0;j<=k;++j) {
ans[j]=(ans[j]-pp+MODD)%MODD;
pp=pp*2*a[i]%MODD;
}
}
for(int i=0;i<=k;++i) {
for(int j=0;j<=i;++j) {
ans[i]=(ans[i]+(LL)sum[n][j]*sum[n][i-j]%MODD*C[i][j]%MODD)%MODD;
}
}
LL i2=ksm(2,MODD-2);
for(int i=1;i<=k;++i) {
printf("%lld\n",ans[i]*i2%MODD);
}
return 0;
}