BZOJ 3157: 国王奇遇记&&3516: 国王奇遇记加强版（扰动法）

Posted On 2018年11月30日

Description

Input

共一行包括两个正整数N和M。

Output

共一行为所求表达式的值对10^9+7取模的值。

Sample Input

5 3

Sample Output

36363

HINT

1<=N<=10^9,1<=M<=200

Source

Katharon+#1

Solution

#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int P=1e9+7,up=1e6,maxn=up+100;
inline int Pow(int a,int b)
{
	int ans=1;
	for (;b;b>>=1,a=1ll*a*a%P)(b&1)&&(ans=1ll*ans*a%P);
	return ans;
}
int s[maxn],fac[maxn],inv[maxn];
inline int C(const int n,const int m)
{
	return 1ll*fac[n]*inv[n-m]%P*inv[m]%P;
}
inline void dec(int&a,int delta)
{
	a=a-delta;
	if (a<0)a+=P;
}
signed main()
{
	int n=read(),m=read();
	if (m==1)
	{
		printf("%d\n",1ll*(1+n)*n%P*Pow(2,P-2)%P);
		return 0;
	}
	fac[0]=1;
	for (int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%P;
	inv[m]=Pow(fac[m],P-2);
	for (int i=m-1;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
	dec(s[0]=Pow(m,n+1),m);
	s[0]=1ll*s[0]*Pow(m-1,P-2)%P;
	for (int k=1;k<=m;k++)
	{
		dec(s[k]=1ll*Pow(n+1,k)*Pow(m,n+1)%P,m);
		for (int j=0;j<k;j++)
			dec(s[k],1ll*C(k,j)*s[j]%P*m%P);
		s[k]=1ll*s[k]*Pow(m-1,P-2)%P;
	}
	printf("%d\n",s[m]);
}

#include <cstring>

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int P=1e9+7,up=1e6,maxn=up+100;

inline int Pow(int a,int b)

{

int ans=1;

for (;b;b>>=1,a=1ll*a*a%P)(b&1)&&(ans=1ll*ans*a%P);

return ans;

}

int s[maxn],fac[maxn],inv[maxn];

inline int C(const int n,const int m)

{

return 1ll*fac[n]*inv[n-m]%P*inv[m]%P;

}

inline void dec(int&a,int delta)

{

a=a-delta;

if (a<0)a+=P;

}

signed main()

{

int n=read(),m=read();

if (m==1)

{

printf("%d\n",1ll*(1+n)*n%P*Pow(2,P-2)%P);

return 0;

}

fac[0]=1;

for (int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%P;

inv[m]=Pow(fac[m],P-2);

for (int i=m-1;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;

dec(s[0]=Pow(m,n+1),m);

s[0]=1ll*s[0]*Pow(m-1,P-2)%P;

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

{

dec(s[k]=1ll*Pow(n+1,k)*Pow(m,n+1)%P,m);

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

dec(s[k],1ll*C(k,j)*s[j]%P*m%P);

s[k]=1ll*s[k]*Pow(m-1,P-2)%P;

}

printf("%d\n",s[m]);

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments