From The Stupid
Bad at Coding
BZOJ 2875: [Noi2012]随机数生成器
starli
posted @ 2016年2月04日 21:58
in 乱搞？
, 451 阅读
今天颓了一天..就A了两简单题
矩阵乘法快速幂 然而long long 是会溢出的我也不知道怎么办 然后 我查了一下快速乘 得到了一个神奇的东西
输入x，y 返回x*y%mod 我也不知道为什么这个可以VB_Z)YH4MSG}6]G)`F.jpg)
听说这篇论文里有说到 论程序底层优化的一些方法与技巧.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;
}
评论 (0)