【BZOJ3157/3516】国王奇遇记（数论）

时间：2021-10-19 06:07:55

【BZOJ3157/3516】国王奇遇记（数论）

题面

BZOJ3157

BZOJ3516

题解

先考虑怎么做\(m\le 100\)的情况、

令\(f(n,k)=\displaystyle \sum_{i=1}^n i^k m^i\)，然后推式子：

\[\begin{aligned}
f(n+1,k)&=\sum_{i=1}^{n+1} i^km^i=m+\sum_{i=2}^{n+1}i^km^i\\
&=m+\sum_{i=1}^n (i+1)^km^{i+1}\\
&=m+m\sum_{i=1}^n m^i\sum_{j=0}^k{k\choose j}i^j\\
&=m+m\sum_{j=0}^{k}{k\choose j}\sum_{i=1}^n i^jm^i\\
&=m+m\sum_{j=0}^k {k\choose j}f(n,j)
\end{aligned}\]

这样子可以做到\(O(nm)\)。

考虑继续处理这个式子：

\[\begin{aligned}
f(2n,k)&=\sum_{i=1}^{2n}i^km^i=f(n,k)+m^n\sum_{i=1}^n (i+n)^km^i\\
&=f(n,k)+m^n\sum_{i=1}^n m^i\sum_{j=0}^k {k\choose j}i^jn^{k-j}\\
&=f(n,k)+m^n\sum_{j=0}^k{k\choose j}n^{k-j}\sum_{i=1}^ni^j m^i\\
&=f(n,k)+m^n\sum_{j=0}^k{k\choose j}n^{k-j}f(n,j)
\end{aligned}\]

既然这样子就可以愉快的倍增了。

时间复杂度\(O(m^2\log n)\)

#include<iostream>

using namespace std;

#define MOD 1000000007

int n,m,f[222],C[222][222],pw[222],tmp[222];

int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}

void Solve(int n)

{

	if(n==1){for(int i=0;i<=m;++i)f[i]=m;return;}

	Solve(n>>1);int pwm=fpow(m,n>>1);

	pw[0]=1;for(int i=1;i<=m;++i)pw[i]=1ll*pw[i-1]*(n>>1)%MOD;

	for(int i=0;i<=m;++i)tmp[i]=f[i];

	for(int k=0;k<=m;++k)

		for(int j=0;j<=k;++j)

			tmp[k]=(tmp[k]+1ll*pwm*C[k][j]%MOD*pw[k-j]%MOD*f[j])%MOD;

	for(int i=0;i<=m;++i)f[i]=tmp[i];

	if(n&1)

	{

		for(int i=0;i<=m;++i)tmp[i]=m;

		for(int k=0;k<=m;++k)

			for(int j=0;j<=k;++j)

				tmp[k]=(tmp[k]+1ll*m*C[k][j]%MOD*f[j])%MOD;

		for(int i=0;i<=m;++i)f[i]=tmp[i];

	}

}

int main()

{

	cin>>n>>m;

	for(int i=0;i<=m;++i)C[i][0]=1;

	for(int i=1;i<=m;++i)

		for(int j=1;j<=i;++j)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;

	Solve(n);

	cout<<f[m]<<endl;

	return 0;

}

然而如果你直接把上面的代码去交加强版就会\(T\)飞（时限\(1s\)）

考虑更加优秀的方法。

直接令\(f(k)=\sum_{i=1}^n i^k m^i\)。

然后拿出来强行做个差：

\[\begin{aligned}
mf(k)-f(k)&=\sum_{i=1}^n i^k m^{i+1}-\sum_{i=1}^n i^km^i\\
&=n^km^{n+1}+\sum_{i=1}^{n} (i-1)^km^i-\sum_{i=1}^n i^k m^i\\
&=n^km^{n+1}+\sum_{i=1}^{n}m^i((i-1)^k-i^k)\\
&=n^km^{n+1}+\sum_{i=1}^n m^i \sum_{j=0}^{k-1}{k\choose j}(-1)^{k-j}i^j\\
&=n^km^{n+1}+\sum_{j=0}^{k-1}{k\choose j}(-1)^{k-j}\sum_{i=1}^n i^jm^i\\
&=n^km^{n+1}+\sum_{j=0}^{k-1}{k\choose j}(-1)^{k-j}f(j)\\
\end{aligned}\]

于是就可以做到\(O(m^2)\)了。

注意\(m=1\)的时候需要特判。

#include<iostream>

using namespace std;

#define MOD 1000000007

int n,m,f[1010],C[1010][1010],pw[1010],tmp[1010];

int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}

int main()

{

	cin>>n>>m;

	if(m==1){cout<<1ll*n*(n+1)/2%MOD<<endl;return 0;}

	int inv=fpow(m-1,MOD-2);

	for(int i=0;i<=m;++i)C[i][0]=1;

	for(int i=1;i<=m;++i)

		for(int j=1;j<=i;++j)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;

	f[0]=1ll*(fpow(m,n)+MOD-1)*inv%MOD*m%MOD;

	for(int k=1,pwm=fpow(m,n+1),pw=n;k<=m;++k,pw=1ll*pw*n%MOD)

	{

		f[k]=1ll*pw*pwm%MOD;

		for(int j=0,d=((k&1)?(MOD-1):1);j<k;++j,d=MOD-d)

			f[k]=(f[k]+1ll*C[k][j]*d%MOD*f[j])%MOD;

		f[k]=1ll*f[k]*inv%MOD;

	}

	cout<<f[m]<<endl;

	return 0;

}

似乎还要一个更强的版本，然而我不会做QwQ。

相关文章