ARC 106 D题解
竟然有蒟蒻会做的 ARC D，泪目。
题目简述：
对于每一个 \(x\leq k\)，求：
\[\left(\sum_{l=1}^{n-1}\sum_{r=l+1}^n \left(a_l+a_r\right)^x\right) \bmod 998244353 \]\[n\leqslant 2\times 10^5,k\leqslant300 \]\[\text{时间限制：3s},\text{空间限制：1GB} \]不保证没有其他神仙一万倍的算法。
这个，关于这种相加求幂的形式，我好像只会二项式定理。
\[\begin{aligned}\sum_{l=i+1}^{n-1}\sum_{r=l+1}^n \left(a_l+a_r\right)^x&=\sum_{l=1}^{n-1}\sum_{r=l+1}^n \sum_{i=0}^x\dbinom{x}{i}a_l^ia_r^{x-i}\cr&=\sum_{i=0}^x\dbinom{x}{i}\sum_{l=1}^{n-1}a_l^i\sum_{r=l+1}^n a_r^{x-i}\end{aligned} \]对于我来说能想到变换求和顺序就很不错了，果真我后面就暂时性卡住了。
开始想到这些东西互相影响，好像变换求和顺序之后并没有什么好处。
那能不能让他不影响？
我直接玩后面哪两个求和，为了方便，先让指数都是 \(1\)。
那么这个东西是 \(a_1a_2+a_1a_3+a_2a_3\) 。
比较难做，但是，
我们知道这种形式是比较好做的：
\[(a_1+a_2+a_3)(a_1+a_2+a_3) \]其实他们差的只是 \(a_i^2\) 和另一个他自己。
考虑加上指数?进一步可以得到：
\[\sum_{l=1}^{n-1}a_l^i\sum_{r=l+1}^n a_r^{x-i}=\sum_{l=1}^n a_l^i\sum_{r=1}^na_r^{x-i}-\sum_{j=1}^n a_j^x-\sum_{l=1}^{n-1}a_{l}^{x-i}\sum_{r=l+1}^na_r^i \]然后这个单求是很不可做的，但是，考虑到：
\(i\) 的枚举范围是 \(0\sim x\)，我们不仅要枚举 \((i,x-i)\) 的系数组合，还要枚举 \((x-i,i)\) 的系数组合。
更重要的是:
\[\dbinom{x}{i}=\dbinom{x}{x-i} \]对上面那个东西移项容易得到：
\[\sum_{l=1}^{n-1}a_l^i\sum_{r=l+1}^n a_r^{x-i}+\sum_{l=1}^{n-1}a_{l}^{x-i}\sum_{r=l+1}^na_r^i=\sum_{l=1}^n a_l^i\sum_{r=1}^na_r^{x-i}-\sum_{j=1}^n a_j^x \]在系数相同的前提下，这个东西完全可以合并起来一起算。
我们发现当 \(2 \nmid x\) 时，正好可以合并 \(\dfrac{x-1}{2}\) 对，那么容易发现最后的答案是：
\[\sum_{i=0}^{\frac{x-1}{2}}\dbinom{x}{i}\left(\sum_{l=1}^na_l^i\sum_{r=1}^na_r^{x-i}-\sum_{j=1}^na_j^x\right) \]我们发现后面这个预处理一下，时间复杂度是 \(\mathcal O(nk)\) 的，对于组合数我们先把阶乘搞出来，每次求就是 \(\mathcal O(\log p)\) 了，总的时间复杂度容易分析为 \(\mathcal O(k^2\log p+nk)\)，对于 ATCoder 的神仙机器和这么大的时空限制（好像和 ATCoder 标准时空差不多......），完全可以过了。
嗯，你又问 \(2 \mid x\) 怎么做。
首先对于除了中间那个 \(\dfrac{x}{2}\) 和上面的算法是一样的。
我们将 \(\dfrac{x}{2}\) 暴力带入上面那个式子可以发现：
\[\sum_{l=1}^{n-1}a_l^{\frac{x}{2}}\sum_{r=l+1}^n a_r^{\frac{x}{2}}=\sum_{l=1}^n a_l^{\frac{x}{2}}\sum_{r=1}^na_r^{\frac{x}{2}}-\sum_{j=1}^n a_j^x-\sum_{l=1}^{n-1}a_{l}^{\frac{x}{2}}\sum_{r=l+1}^na_r^{\frac{x}{2}} \]然后容易解出：
\[\sum_{l=1}^{n-1}a_l^{\frac{x}{2}}\sum_{r=l+1}^n a_r^{\frac{x}{2}}=\dfrac{1}{2}\left(\sum_{l=1}^n a_l^{\frac{x}{2}}\sum_{r=1}^na_r^{\frac{x}{2}}-\sum_{j=1}^n a_j^x\right) \]我们手算就能得到 \(2\) 在 \(\bmod 998244353\) 意义下的逆元是 \(499122177\)。
总结一下：
\[ans=\begin{cases}\sum\limits_{i=0}^{\frac{x-1}{2}}\dbinom{x}{i}\left(\sum\limits_{l=1}^na_l^i\sum\limits_{r=1}^na_r^{x-i}-\sum\limits_{j=1}^na_j^x\right) &2 \nmid x\\\sum\limits_{i=0}^{\frac{x}{2}-1}\dbinom{x}{i}\left(\sum\limits_{l=1}^na_l^i\sum\limits_{r=1}^na_r^{x-i}-\sum\limits_{j=1}^na_j^x\right)+\dfrac{1}{2}\dbinom{x}{\frac{x}{2}}\left(\sum\limits_{l=1}^n a_l^{\frac{x}{2}}\sum\limits_{r=1}^na_r^{\frac{x}{2}}-\sum\limits_{j=1}^n a_j^x\right)&2\mid x\end{cases} \]下面是参考代码：
#include"iostream"
#include"cstdio"
#include"cmath"
#include"cstring"
#include"algorithm"
#include"stack"
#include"queue"
using namespace std;
#define read(x) scanf("%d",&x)
#define readl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define MOD 998244353
#define MAXN 200005
int n,k;
ll sum[305],Cs[305];
ll fac[305];
ll a[MAXN];
ll quickpow(ll a,ll b)
{
ll ans=1,base=a;
while(b)
{
if(b&1) ans=ans*base%MOD;
b>>=1;
base=base*base%MOD;
}
return ans%MOD;
}
ll inv(ll a){return quickpow(a,MOD-2)%MOD;}
int main()
{
read(n),read(k);
fac[0]=1ll;
for(int i=1;i<=n;i++) readl(a[i]);
for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%MOD;
for(int i=1;i<=n;i++)
{
ll op=1ll;
for(int j=0;j<=k;j++)
{
sum[j]=(sum[j]+op)%MOD;
op=op*a[i]%MOD;
}
}
for(int x=1;x<=k;x++)
{
ll ans=0;
if(x&1)
{
for(int i=0;i<=x/2;i++)
{
ll c=fac[x]*inv(fac[x-i]*fac[i]%MOD)%MOD;
ll now=(sum[i]*sum[x-i]-sum[x]+MOD)%MOD;
ans=(ans+now*c%MOD)%MOD;
}
}
else
{
for(int i=0;i小日本（的神机果然厉害，只跑了 \(260ms\) /jk。