bzoj2875随机数生成器

妖狐艹你老母 2021-09-29 17:20 249阅读 0赞

题目：[https://www.lydsy.com/JudgeOnline/problem.php?id=2875][https_www.lydsy.com_JudgeOnline_problem.php_id_2875]

矩阵乘裸题。

如果直接乘的话会爆long long，所以用加法代替乘，过程中不断取模。

加法应是快速乘，不要O(n)循环……

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    ll n,m,g,a,c,ans,x;
    ll mul(ll u,ll v)
    {
        ll ret=0,tp=u;
        while(v)
        {
            if(v&1)(ret+=tp)%=m;
            (tp+=tp)%=m;v>>=1;
        }
        return ret;
    }
    struct Matrix{
        ll v[2][2];
        Matrix operator *(const Matrix &b)const
        {
            Matrix tp;memset(tp.v,0,sizeof tp.v);
            for(int i=0;i<=1;i++)
                for(int j=0;j<=1;j++)
                    for(int k=0;k<=1;k++)
                        (tp.v[i][j]+=mul(v[i][k],b.v[k][j]))%=m;
            return tp;
        }
    }res,ct;
    void init()
    {
        scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x,&n,&g);
        n--;
        res.v[0][0]=a;res.v[0][1]=1;
        res.v[1][0]=0;res.v[1][1]=1;
        memcpy(ct.v,res.v,sizeof res.v);
    }
    int main()
    {
        init();
        while(n)
        {
            if(n&1)res=res*ct;
            ct=ct*ct;n>>=1;
        }
        ans=(mul(res.v[0][0],x)+mul(res.v[0][1],c))%m%g;
        printf("%lld",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/Narh/p/9043488.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_2875]: https://www.lydsy.com/JudgeOnline/problem.php?id=2875

发表评论取消回复

表情：

评论列表（有 0 条评论，249人围观）

还没有评论，来说两句吧...

相关阅读

相关 java伪随机数生成器

关于随机数的基本概念 1、对随机数性质分类：随机性：符合该性质的叫弱伪随机数。这种随机数仅可以用于一般应用，无法用在密码学，例如java中的java.util.

港控/mmm°/ 2024年03月29日 15:45/ 0 赞/ 102 阅读

相关随机数生成器代码HTML5

代码如下 -------------------- <!DOCTYPE html> <html> <head> <title>随机数生成器</title>

小咪咪/ 2024年03月01日 08:00/ 0 赞/ 53 阅读

相关【Java】简单随机数生成器

前几年部门开始推行“抓阄”领任务的工作模式，当时写了一个简单的随机数生成器。 RESTful入口 ![在这里插入图片描述][watermark_type_ZmFuZ3p

一时失言乱红尘/ 2022年11月12日 02:40/ 0 赞/ 207 阅读

相关 OpenCV学习(十一)之随机数生成器RNG

OpenCV中C++的RNG类可以压缩一个64位的i整数并可以得到scalar和array的随机数。目前的版本支持均匀分布随机数和Gaussian分布随机数。随机数的产生采用的

超、凢脫俗/ 2022年08月05日 20:28/ 0 赞/ 555 阅读

相关纯线性同余随机数生成器

1. 线性同余随机数生成器介绍：古老的LCG(linear congruential generator)代表了最好最朴素的伪随机数产生器算法。主要原因是容易理解，容易实

我不是女神ヾ/ 2022年08月05日 11:12/ 0 赞/ 34 阅读

相关 BZOJ1030 [JSOI2007] 文本生成器

我再看错模数我就是呆头考虑包含任意的补集不包含任何然后典型的AC自动机上dp 长度为l不能走到任何关键点特么模数多写了个0 问题是我刚跟zyf吐槽了模数就当考前

朱雀/ 2021年12月23日 06:19/ 0 赞/ 254 阅读

相关洛谷P3306 随机数生成器

题意：给你一个数列，a1 = x，ai = (A \ ai-1 \+ B) % P，求第一个是t的是哪一项，或者永远不会有t。解：循环节不会超过P。我们使用BSGS的思想，

野性酷女/ 2021年12月22日 16:45/ 0 赞/ 308 阅读

相关 bzoj2875随机数生成器

题目：[https://www.lydsy.com/JudgeOnline/problem.php?id=2875][https_www.lydsy.com_JudgeOnli

妖狐艹你老母/ 2021年09月29日 17:20/ 0 赞/ 250 阅读

相关浅谈随机数生成器及其应用

　　再一次向YYF大神致敬。　　但有一个叫YYF的大神（它说自己是蒟蒻）叫我附上转载地址：[/images/20210725/b418f7e0ca6a4b8f82eb

缺乏、安全感/ 2021年09月29日 09:14/ 0 赞/ 462 阅读

相关 Random.org -- 真正的随机数生成器

接触过程序设计的人一定对随机数不陌生。随机数的用途非常广，比方在測试、分布和统计程序、游戏中。大多数编程语言也提供了随机数库。能够方便的使用。只是从严格意义上来讲，这些

超、凢脫俗/ 2021年09月29日 06:28/ 0 赞/ 673 阅读