BZOJ 2875: [Noi2012]随机数生成器

starli posted @ 2016年2月04日 21:58 in 乱搞? , 165 阅读
今天颓了一天..就A了两简单题
矩阵乘法快速幂 然而long long 是会溢出的我也不知道怎么办 然后 我查了一下快速乘 得到了一个神奇的东西 
输入x,y 返回x*y%mod 我也不知道为什么这个可以 
听说这篇论文里有说到 论程序底层优化的一些方法与技巧.pdf
inline long long multi(long long x,long long y,long long mod){
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
在vijos上又看到一种方法 把快速幂的思想用到乘法上来,就变成了每次被乘数倍增乘数除二了,logn的乘法也是可过的而且是精确计算而不是像上面这样近似计算
 
总之扒了这个代码之后就过了
#include <cstdio>
using namespace std;
typedef long long LL;
LL a,x,c,n,m,g;
inline long long multi(long long x,long long y,long long mod){
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
struct mat{
	LL a[4][4];
	void reset(){for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j]=0;}
	void set1(){reset();for(int i=0;i<4;i++) a[i][i]=1;}
	friend mat operator *(mat x,mat y){
		mat z;
		z.reset();
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				for(int k=0;k<=3;k++) (z.a[i][j]+=multi(x.a[i][k],y.a[k][j],m))%=m;
		return z;
	}
}o,tmp,ans;

int main(){
	scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x,&n,&g);
	a%=m,c%=m,x%=m;
	tmp.reset();tmp.a[1][1]=a;tmp.a[2][1]=c;tmp.a[2][2]=1;
	o.reset();o.a[1][1]=x;o.a[1][2]=1;
	ans.set1();
	for(;n;n>>=1){if(n&1) ans=ans*tmp;tmp=tmp*tmp;}
	ans=o*ans;
	printf("%lld",ans.a[1][1]%m%g);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter