首页 > 代码库 > BZOJ2875 [Noi2012]随机数生成器
BZOJ2875 [Noi2012]随机数生成器
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
Input
包含6个用空格分割的m,a,c,X0,n和g，其中a,c,X0是非负整数，m,n,g是正整数。
Output
输出一个数，即Xn mod g
Sample Input
11 8 7 1 5 3
Sample Output
2
正解：矩乘快速幂+快速乘法（or long double黑科技乘法）
解题报告：
就是一个矩乘裸题。
构造一个第一行为$[a,0]$,第二行为$[c,1]$，然后根据结合律，矩乘快速幂即可。
开始我写的是快速乘法（龟速乘法），多了一个$log$。
突然想起可以试试学过但是一直没用的$double$黑科技乘法，可以做到$O(1)$的$long$ $long$*$long$ $long$，写了一发，$WA$了很久之后终于发现我自己$yy$的是一个错的。
转型太多导致精度爆炸了。
考虑没有必要转过来转过去地做，可以用$long long$直接做，因为高位必然相等，而我只要$long long$部分的结果，而直接做相当于对$2^{64}$取模，没有问题...
龟速乘法：
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
LL m,a,c,X0,n,g;
struct Matrix{
LL s[2][2];
}A,B,ini;
inline LL cheng(LL x,LL y){
LL r=0;
while(y>0) {
if(y&1) r+=x,r%=m;
x+=x; x%=m;
y>>=1;
}
return r;
}
inline Matrix operator * (Matrix q,Matrix qq){
Matrix tmp=ini;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int l=0;l<2;l++)
tmp.s[i][j]+=cheng(q.s[i][l],qq.s[l][j]),tmp.s[i][j]%=m;
return tmp;
}
inline LL getLL(){
LL w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void fast_pow(Matrix a,LL y){
B.s[0][0]=B.s[1][1]=1;
while(y>0) {
if(y&1) B=B*a;
a=a*a;
y>>=1;
}
}
inline void work(){
m=getLL(); a=getLL(); c=getLL(); X0=getLL(); n=getLL(); g=getLL();
A.s[0][0]=a; A.s[0][1]=0; A.s[1][0]=c; A.s[1][1]=1;
fast_pow(A,n);
printf("%lld",((cheng(X0,B.s[0][0])+B.s[1][0])%m)%g);
}
int main()
{
work();
return 0;
}
long double 黑科技：
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
LL m,a,c,X0,n,g;
struct Matrix{
LL s[2][2];
}A,B,ini;
inline LL cheng(LL x,LL y){//double快速乘法
long double sum=(long double)x*y;
long double d=(long double)sum/m; LL zz=d+1e-6;//防止精度误差
LL r=x*y-zz*m; r%=m; r+=m; r%=m;//可以直接做，因为高位必然相等，而我只要long long部分的结果，而直接做相当于对2^64取模，没有问题
return r;
}
inline Matrix operator * (Matrix q,Matrix qq){
Matrix tmp=ini;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int l=0;l<2;l++)
tmp.s[i][j]+=cheng(q.s[i][l],qq.s[l][j]),tmp.s[i][j]%=m;
return tmp;
}
inline LL getLL(){
LL w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void fast_pow(Matrix a,LL y){
B.s[0][0]=B.s[1][1]=1;
while(y>0) {
if(y&1) B=B*a;
a=a*a;
y>>=1;
}
}
inline void work(){
m=getLL(); a=getLL(); c=getLL(); X0=getLL(); n=getLL(); g=getLL();
A.s[0][0]=a; A.s[0][1]=0; A.s[1][0]=c; A.s[1][1]=1;
fast_pow(A,n);
printf("%lld",((cheng(X0,B.s[0][0])+B.s[1][0])%m)%g);
}
int main()
{
work();
return 0;
}
BZOJ2875 [Noi2012]随机数生成器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。