现在还有企业做网站吗,做百度推广送的网站,中国建筑集团公司官网,天津网站建设案例正题
题目链接:https://www.luogu.com.cn/problem/P5437 题目大意 nnn个点的完全图#xff0c;连接i,ji,ji,j的边权值为(ij)k(ij)^k(ij)k。随机选出一个生成树#xff0c;求期望边权和。 1≤n998244353,1≤k≤1071\leq n998244353,1\leq k\leq 10^71≤n99824435…正题
题目链接:https://www.luogu.com.cn/problem/P5437 题目大意
nnn个点的完全图连接i,ji,ji,j的边权值为(ij)k(ij)^k(ij)k。随机选出一个生成树求期望边权和。
1≤n998244353,1≤k≤1071\leq n998244353,1\leq k\leq 10^71≤n998244353,1≤k≤107 解题思路
一条边选出来的概率是2n\frac{2}{n}n2总共有2n(n−1)\frac{2}{n(n-1)}n(n−1)2条选n−1n-1n−1条或者PruferPruferPrufer序列也能证明
所以现在考虑怎么求 ∑i1n∑j1n(ij)k\sum_{i1}^n\sum_{j1}^n(ij)^ki1∑nj1∑n(ij)k 这个东西首先f(n)∑i1n∑j1nijf(n)\sum_{i1}^n\sum_{j1}^nijf(n)∑i1n∑j1nij是一个二项式所以(ij)k(ij)^k(ij)k就是一个k2k2k2次多项式所以可以考虑用拉插。
现在是如何快速求出1∼k1\sim k1∼k的值考虑递推 f(n)−f(n−1)∑i1n∑j1n(ij)k−∑i1n−1∑j1n−1(ij)kf(n)-f(n-1)\sum_{i1}^n\sum_{j1}^n(ij)^k-\sum_{i1}^{n-1}\sum_{j1}^{n-1}(ij)^kf(n)−f(n−1)i1∑nj1∑n(ij)k−i1∑n−1j1∑n−1(ij)k ∑in12n−1ik\sum_{in1}^{2n-1}i^kin1∑2n−1ik
然后用线性筛预处理出iki^kik就好了。当然拉插也要用线性的优化
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e710,P998244353;
ll n,k,cnt,pri[N/5],w[N1],y[N];
ll pre[N],suf[N],inv[N],ans;
bool v[N1];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void Prime(int n){w[1]1;for(ll i2;in;i){if(!v[i])pri[cnt]i,w[i]power(i,k);for(ll j1;jcnti*pri[j]n;j){v[i*pri[j]]1;w[i*pri[j]]w[i]*w[pri[j]]%P;if(i%pri[j]0)break;}}return;
}
signed main()
{scanf(%lld%lld,n,k);Prime(k*26);k3;pre[0]suf[k1]inv[1]1;y[2]w[3];for(ll i3;ik;i)y[i](y[i-1]w[i*2-1]w[i*2-2]-w[i])%P;for(ll i1;ik;i)y[i](y[i-1]y[i])%P;for(ll i1;ik;i)pre[i]pre[i-1]*(n-i)%P;for(ll ik;i1;i--)suf[i]suf[i1]*(n-i)%P;for(ll i2;ik;i)inv[i]P-inv[P%i]*(P/i)%P;inv[0]1;for(ll i1;ik;i)inv[i]inv[i-1]*inv[i]%P;for(ll i1;ik;i)(anspre[i-1]*suf[i1]%P*inv[i-1]%P*inv[k-i]%P*y[i]%P*(((k-i)1)?-1:1))%P;printf(%lld\n,(ansP)%P*power(n,P-2)%P*2%P);return 0;
}
