bzoj2875随机数生成器

妖狐艹你老母 2021-09-29 17:20 192阅读 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 条评论，192人围观）

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

相关阅读

相关 java伪随机数生成器

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

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

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

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

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

相关 c 语言随机值的生成器,C 语言随机数生成器的实现分析

原标题：C 语言随机数生成器的实现分析 (点击上方公众号，可快速关注) 来源：伯乐在线 - 卢亮如需转载，发送「转载」二字查看说明本文是为了记录和澄清一个由来已久

柔光的暖阳◎/ 2022年10月15日 05:56/ 0 赞/ 145 阅读

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

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

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

相关 Java中的随机数生成器：Random，ThreadLocalRandom，SecureRandom

文中的 Random即：java.util.Random， ThreadLocalRandom 即：java.util.concurrent.ThreadLocalRan

素颜马尾好姑娘i/ 2022年03月02日 14:10/ 0 赞/ 216 阅读

相关 BZOJ1030 [JSOI2007] 文本生成器

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

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

相关洛谷P3306 随机数生成器

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

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

相关 bzoj2875随机数生成器

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

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

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

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

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

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

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

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