当前位置:网站首页>【矩阵乘】【NOI 2012】【cogs963】随机数生成器
【矩阵乘】【NOI 2012】【cogs963】随机数生成器
2022-07-07 20:03:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
963. [NOI2012] 随机数生成器
** 输入文件:randoma.in 输出文件:randoma.out 简单对照
时间限制:1 s 内存限制:128 MB
**【问题描写叙述】
栋栋近期迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列。这样的方法须要设置四个非负整数參数m,a,c,X[0],依照以下的公式生成出一系列随机数{Xn}:
X[n+1]=(aX[n]+c) mod m
当中mod m表示前面的数除以m的余数。从这个式子能够看出,这个序列的下一个数总是由上一个数生成的。
用这样的方法生成的序列具有随机序列的性质。因此这样的方法被广泛地使用,包括经常使用的C++和Pascal的产生随机数的库函数使用的也是这样的方法。
栋栋知道这样产生的序列具有良好的随机性,只是心急的他仍然想尽快知道X[n]是多少。
由于栋栋须要的随机数是0,1,…,g-1之间的,他须要将X[n]除以g取余得到他想要的数,即X[n] mod g,你仅仅须要告诉栋栋他想要的数X[n] mod g是多少就能够了。
【输入格式】
输入文件randoma.in中包括6个用空格切割的整数m,a,c,X[0],n和g,当中a,c,X[0]是非负整数。m,n,g是正整数。
【输出格式】
输出到文件randoma.out中,输出一个数,即X[n] mod g
【例子输入】
11 8 7 1 5 3
【例子输出】
2
【例子说明】
计算得X[n]=X[5]=8,故(X[n] mod g) = (8 mod 3) = 2
【数据规模】
40%的数据中m为质数
30%的数据中m与a-1互质
50%的数据中n<=10^6
100%的数据中n<=10^18
40%的数据m,a,c,X[0]<=10^4
85%的数据m,a,c,X[0]<=10^9
100%的数据中m,a,c,X[0]<=10^18
100%的数据中g<=10^8
对于全部数据,n>=1,m>=1,a>=0,c>=0,X[0]>=0,g>=1。
题解:
比較简单的矩阵乘,对于两个矩阵:
A[a,c0,1]
B[X[n−1]1]
显然,X[n]能够由这两个矩阵相乘得到: A∗B=C[X[n]1]
于是对于X[n],我们能够这样求: An∗[X[0]1]
比較坑人的是须要写高速乘,由于普通乘会炸。。。 (PS:高速乘差点儿和高速幂写起来一样,仅仅须要把 * 改成 +)
Code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long A[2][2]={{0,0},{0,1}},B[2][2]={{0,0},{1,0}},C[2][2]={0};
long long n,g,m,nn;
long long kc(long long x,long long y){
long long z=0;
x%=m; y%=m;
if (x<y) swap(x,y);
while (y){
if (y&1) z=(z+x)%m;
x=(2*x)%m;
y>>=1;
}
return z;
}
int main(){
scanf("%lld%lld%lld%lld%lld%lld",&m,&A[0][0],&A[0][1],&B[0][0],&n,&g);
nn=n;
while (nn){
if (nn&1){
memset(C,0,sizeof(C));
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
for (int k=0; k<2; k++)
C[i][j]=(C[i][j]+kc(A[i][k],B[k][j]))%m;
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
B[i][j]=C[i][j];
}
nn>>=1;
memset(C,0,sizeof(C));
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
for (int k=0; k<2; k++)
C[i][j]=(C[i][j]+kc(A[i][k],A[k][j]))%m;
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
A[i][j]=C[i][j];
}
printf("%lld\n",B[0][0]%g);
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116386.html原文链接:https://javaforall.cn
边栏推荐
- VMWare中虚拟机网络配置
- Jenkins 用户权限管理
- MySQL约束之默认约束default与零填充约束zerofill
- 2022如何评估与选择低代码开发平台?
- Écrivez une liste de sauts
- Mysql子查询关键字的使用方式(exists)
- [award publicity] issue 22 publicity of the award list in June 2022: Community star selection | Newcomer Award | blog synchronization | recommendation Award
- 【网络原理的概念】
- Apifox 接口一体化管理新神器
- DataTable数据转换为实体
猜你喜欢
解决使用uni-app MediaError MediaError ErrorCode -5
测量楼的高度
上海交大最新《标签高效深度分割》研究进展综述,全面阐述无监督、粗监督、不完全监督和噪声监督的深度分割方法
【C语言】指针进阶---指针你真的学懂了吗?
使用枚举实现英文转盲文
让这个CRMEB单商户微信商城系统火起来,太好用了!
Helix QAC 2020.2新版静态测试工具,最大限度扩展了标准合规性的覆盖范围
VMWare中虚拟机网络配置
How to meet the dual needs of security and confidentiality of medical devices?
恶魔奶爸 B3 少量泛读,完成两万词汇量+
随机推荐
【函数递归】简单递归的5个经典例子,你都会吗?
Airiot helps the urban pipe gallery project, and smart IOT guards the lifeline of the city
有用的win11小技巧
Deep learning model compression and acceleration technology (VII): mixed mode
Numerical method for solving optimal control problem (0) -- Definition
Implement secondary index with Gaussian redis
Referrer和Referrer-Policy简介
Write a jump table
You want to kill a port process, but you can't find it in the service list. You can find this process and kill it through the command line to reduce restarting the computer and find the root cause of
Spark judges that DF is empty
FTP steps for downloading files from Huawei CE switches
Micro service remote debug, nocalhost + rainbow micro service development second bullet
Jenkins 用户权限管理
4G设备接入EasyGBS平台出现流量消耗异常,是什么原因?
不落人后!简单好用的低代码开发,快速搭建智慧管理信息系统
Update iteration summary of target detection based on deep learning (continuous update ing)
npm uninstall和rm直接删除的区别
Make this crmeb single merchant wechat mall system popular, so easy to use!
备份 TiDB 集群到持久卷
Implement secondary index with Gaussian redis