传送门
非常舒适的一道题 趁机学了一发拉格朗日插值2333
貌似是WC2018讲的题
我们对于在原图中存在的边 记为x 没出现的边记为1
然后矩阵树定理求出行列式 对应的x^k的系数就是跟原图有k条重边的方案数
显然带多项式进去不好算
那么我们拉格朗日插值 对于x分别算1-n得到了n个值
然后插值回来就可以了
【题解|CF917D Stranger Trees】拉格朗日求系数我也没有找到好的博客 于是找到学长求助 结果他们说的我很懵逼【大概是我菜的真实
于是自己YY了一个
拉格朗日插值的公式是这个
文章图片
感性理解就是 当x = x_i的时候 分式的值=1 *yi就是原式 所以说这个柿子长这样
对于分母很好求 就是 一个常数
分子比较麻烦 我们可以预处理出
文章图片
的值
然后除以(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
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 题解|【HNOI2017】大佬-dalao
- 2019 GDUT Rating Contest #II 这是群题解,七篇!!!
- # 2019 GDUT Rating Contest #I H. Mixing Milk
- # 2019 GDUT Rating Contest #I A. The Bucket List
- # 2019 GDUT Rating Contest #I G. Back and Forth
- 2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解
- 2019 GDUT Winter Personal Training Contest I (Div. 2) A. Protect Sheep
- 题解|题解 | K-ary Heap-2019牛客暑期多校训练营第六场F题
- ACM|[dsu] codeforces 375D. Tree and Queries
- 题解|[BZOJ3817] Sum