【BZOJ3601】一个人的数论 高斯消元+莫比乌斯反演

【BZOJ3601】一个人的数论

题解：本题的做法还是很神的~

那么g(n)如何求呢？显然它的常数项=0，我们可以用待定系数法，将n=1...d+1的情况代入式子中解方程，有d+1个方程和d+1个未知数，直接高斯消元解出ai即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const ll P=1000000007;

int d,n;

ll ans;

ll v[110][110],pa[1010],pb[1010];

ll pm(ll x,ll y)

{

	ll z=1;

	while(y)

	{

		if(y&1)	z=z*x%P;

		x=x*x%P,y>>=1;

	}

	return z;

}

void gauss()

{

	int i,j,k;

	for(i=1;i<=d+1;i++)

	{

		for(j=i;j<=d+1;j++)	if(v[j][i])	break;

		if(i!=j)	for(k=i;k<=d+2;k++)	swap(v[i][k],v[j][k]);

		ll tmp=pm(v[i][i],P-2);

		for(k=i;k<=d+2;k++)	v[i][k]=v[i][k]*tmp%P;

		for(j=1;j<=d+1;j++)	if(i!=j)

		{

			tmp=v[j][i];

			for(k=i;k<=d+2;k++) v[j][k]=(v[j][k]-tmp*v[i][k]%P+P)%P;

		}

	}

}

int main()

{

	scanf("%d%d",&d,&n);

	int i,j;

	for(i=1;i<=d+1;i++)

	{

		for(j=1;j<=d+1;j++)	v[i][j]=pm(i,j);

		for(j=1;j<=i;j++)	v[i][d+2]=(v[i][d+2]+pm(j,d))%P;

	}

	gauss();

	for(i=1;i<=n;i++)	scanf("%lld%lld",&pa[i],&pb[i]);

	for(i=1;i<=d+1;i++)

	{

		ll tmp=1;

		for(j=1;j<=n;j++)

		{

			tmp=tmp*(pm(pa[j],pb[j]*i)-pm(pa[j],d+(pb[j]-1)*i)%P+P)%P;

		}

		ans=(ans+tmp*v[i][d+2]%P)%P;

	}

	printf("%lld",ans);

	return 0;

}//3 2 2 1 5 1