锐客网

  1. 首页 > it技术 > >

题解|CF917D Stranger Trees

题解矩阵树定理拉格朗日插值

传送门
非常舒适的一道题 趁机学了一发拉格朗日插值2333
貌似是WC2018讲的题
我们对于在原图中存在的边 记为x 没出现的边记为1
然后矩阵树定理求出行列式 对应的x^k的系数就是跟原图有k条重边的方案数
显然带多项式进去不好算
那么我们拉格朗日插值 对于x分别算1-n得到了n个值
然后插值回来就可以了
【题解|CF917D Stranger Trees】拉格朗日求系数我也没有找到好的博客 于是找到学长求助 结果他们说的我很懵逼【大概是我菜的真实
于是自己YY了一个
拉格朗日插值的公式是这个
题解|CF917D Stranger Trees
文章图片

感性理解就是 当x = x_i的时候 分式的值=1 *yi就是原式 所以说这个柿子长这样
对于分母很好求 就是 一个常数
分子比较麻烦 我们可以预处理出题解|CF917D Stranger Trees
文章图片
的值
然后除以(x-x_i)就可以了 这个过程可以模拟大除法
取模的话就按照费马小定理取就可以了
写起来非常舒服。
附代码。

#include #include #include #include #define mdn 1000000007 #define mxn 110 #define ll long long using namespace std; int x[mxn],y[mxn]; int k[mxn],p[mxn]; int ksm(int bs,int mi) { int ans=1; while(mi) { if(mi&1)ans=(ll)bs*ans%mdn; bs=(ll)bs*bs%mdn; mi>>=1; } return ans; } bool edg[mxn][mxn]; int n; int lt[mxn],d[mxn]; void get() { p[0]=1; for(int i=1; i<=n; i++) { memcpy(lt,p,sizeof(p)); memset(p,0,sizeof(p)); for(int j=i; ~j; j--) { p[j+1]=(p[j+1]+lt[j])%mdn; p[j]=(p[j]+(ll)lt[j]*(mdn-x[i])%mdn)%mdn; } } } int aa[mxn]; void lagrange(int pos) { int fm=1; for(int i=1; i<=n; i++) if(i!=pos) fm=(ll)fm*(mdn+x[pos]-x[i])%mdn; fm = ksm(fm,mdn-2); fm =(ll)fm*y[pos]%mdn; memcpy(lt,p,sizeof(lt)); for(int i=n; i; i--) { aa[i-1]=lt[i]; lt[i-1]=((ll)lt[i-1]+(ll)lt[i]*x[pos]%mdn+mdn)%mdn; } for(int i=n; ~i; i--) k[i]=((ll)k[i]+(ll)fm*aa[i]%mdn)%mdn; }struct mat{int x[mxn][mxn]; int n; }m; int det() { int f=1,j; for(int i=1; i<=m.n; i++) { if(!m.x[i][i]) { for(j=i+1; j<=m.n; j++) if(m.x[j][i]) break; if(j>m.n) return 0; swap(m.x[j],m.x[i]); f=-f; } for(j=i+1; j<=m.n; j++) { int d=(ll)m.x[j][i]*ksm(m.x[i][i],mdn-2)%mdn; for(int k=i; k<=m.n; k++) { m.x[j][k] -=(ll)m.x[i][k]*d%mdn; if(m.x[j][k]<0) m.x[j][k]+=mdn; } } } int ans=1; for(int i=1; i<=m.n; i++) ans =(ll)ans*m.x[i][i]%mdn; return (mdn+ans*f)%mdn; }int build(int v) { memset(m.x,0,sizeof(m.x)); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) continue; else if(edg[i][j]) m.x[i][j]-=v,m.x[i][i]+=v; else m.x[i][j]--,m.x[i][i]++; } } m.n=n-1; return det(); }int main() { scanf("%d",&n); int uu,vv; for(int i=1; i


    推荐阅读


    上一篇：HashMap(jdk8)

    下一篇：JQuery Easy UI 使用