#C. 代数
欢迎收看 \(T3\) 爆标解法！
额，在此感谢一下 Jijidawang 的帮助，式子从 \(n^2\) 到 \(nk\) 基本都是他做的，（没办法，我太菜了。。。）
节点 \(x\) 在其子树大小为 \(i\) 时的方案数为 \(\dbinom{n-i-1}{x-2}\),然后我们就有了 \(n^2\) 解法，设总方案数为 \(cnt_x\)
\[\sum_{x=1}^{n}a_x\frac{\displaystyle\sum_{i=1}^{n-x+1} i^k\dbinom{n-i-1}{x-2}}{cnt_x}
\]
先放个公式，范德蒙德卷积：$$\displaystyle\sum_{i=0}^{n}\dbinom{i}{a}\dbinom{n-i}{b}=\dbinom{n+1}{a+b+1}$$
然后就可以推了，尝试把后一个求和用一些奇奇怪怪的东西搞出来
\[\sum_{i=0}^{n-x+1}i^k\dbinom{n-i-1}{x-2}
\]
令 \(i=n-i+1\)
\[\sum_{i=0}^{n-1}(n-i-1)^k\dbinom{i}{x-2}=\sum_{i=0}^{n-2}(n-i-1)^k\dbinom{i}{x-2}
\]
于是乎$$cnt_x=\sum_{i=0}^{n-2}\dbinom{i}{x-2}= \sum_{i=0}^{n-2}\dbinom{i}{x-2}\dbinom{n-2-i}{0}=\dbinom{n-1}{x-1}$$
再来一个奇奇怪怪的东西，普通幂转下降幂：$$x^n=\displaystyle\sum_{k}{n\brace k}x^{\underline k}$$
我们令 \(c_i={n\brace k}*i!\)
\[x^k=\sum_{i=0}^kc_i\frac{x^\underline i}{i!}=\sum_{i=0}^kc_i\frac{x^i}{i!(n-i)!}=\sum_{i=0}^kc_i\dbinom{x}{i}
\]
代入原式得
\[\sum_{j=0}^kc_j\sum_{i=0}^{n-1}\dbinom{n-i-1}j\dbinom{i}{x-2}
\]
在此利用一开始那个抽象公式得到
\[\sum_{j=0}^kc_j\dbinom{n}{x+j-1}
\]
然后我们就可以 \(nk\) 做了
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
const int maxn=1e5+100;
using namespace std;
int n,a[maxn],k,ans,jc[maxn],ny[maxn<<1],jcny[maxn<<1],s[21][21],ct[21];
inline int mo(int x){return x>mod?x%mod:x;}
int qpow(int x,int y)
{
int ans=1;
while(y)
{
if(y&1) ans=mo(ans*x);
x=mo(x*x);
y>>=1;
}
return ans;
}
void pre()
{
jc[0]=jc[1]=ny[0]=ny[1]=jcny[0]=jcny[1]=1;
for(int i=2;i<=n+k;i++)
{
ny[i]=(mod-(mod/i)*ny[mod%i]%mod)%mod;
jcny[i]=jcny[i-1]*ny[i]%mod;
jc[i]=jc[i-1]*i%mod;
}
s[0][0]=1;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
s[i][j]=mo(s[i-1][j-1]+j*s[i-1][j]);
}
}
}
int c(int n,int m)
{
if(m>n) return 0;
return jc[n]*jcny[m]%mod*jcny[n-m]%mod;
}
signed main()
{
freopen("algebra.in","r",stdin);
freopen("algebra.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
pre();
for(int i=1;i<=k;i++)
ct[i]=mo(s[k][i]*jc[i]);
for(int x=1;x<=n;x++)
{
int temp=0,cnt=0;
for(int i=0;i<=k;i++)
{
temp=mo(temp+c(n,x+i-1)*ct[i]);
}
cnt=c(n-1,x-1);
temp=mo(temp*qpow(cnt,mod-2));
ans=mo(ans+a[x]*temp);
}
cout<<ans<<endl;
return 0;
}
参考文献(?)
2023.8.1 闲话
二项式反演、斯特林数、Min-max 容斥