首页 > 其他分享 >矩阵游戏

矩阵游戏

时间:2023-08-12 11:44:49浏览次数:38  
标签:游戏 最后 矩阵 一行 000 long 第一项

4954: 矩阵游戏
时间限制(普通/Java):2000MS/6000MS 内存限制:65536KByte

描述

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:
F[1][1]=1
F[i,j]=aF[i][j-1]+b (j!=1)
F[i,1]=c
F[i-1][m]+d (i!=1)
递推式中a,b,c,d都是给定的常数。
现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大,你只需要输出F[n][m]除以1,000,000,007的余数。

输入

一行有六个整数n,m,a,b,c,d。意义如题所述。
1<=N,M<=10^1000 000,a<=a,b,c,d<=10^9

输出

包含一个整数,表示F[n][m]除以1,000,000,007的余数

样例输入

3 4 1 3 2 6

样例输出

85

思路
矩阵快速幂 加 费马小定理 缩小 n 和 m

每一行前一项 往 下一项变换的矩阵为

每一行 最后一项 往 下一行第一项 变化的矩阵为

易得每行第一项向下一行第一项的变换的矩阵为

那第一行第一项往最后一行第一项变化的矩阵为

最后,最后一行第一项往最后一行最后一项变化的矩阵为

合起来就是

得出第一行第一项往最后一行最后一项的转移公式后,还需要缩小 n 和 m

矩阵乘法 也满足 费马小定理

在该定理中

当a!=1时,用这个公式

当a==1 时 用这个公式

证明在这 https://oi-wiki.org/math/number-theory/fermat/

矩阵乘法也类似

这题用到的矩阵的[2][2]位置已经为1 所以需要判断[1][1]位置的数是否为 1

即 特判 的 [1][1]位置的数

因为矩阵只有两个位置的数有影响,我这里把矩阵压缩成两个数来计算,计算过程能更快

AC代码

#include <bits/stdc++.h>
using namespace std;
long long t,w,p=1e9+7;

class Node
{
public:
    long long x,y;
}x,y,z;
long long Change(string s,long long mod)
{
    long long ans=0;
    int len=s.length();
    for(int i=0;i<len;i++)
        ans=(ans*10+s[i]-'0')%mod;
    return ans;
}
Node operator*(Node a,Node b)
{
    return(Node){a.x*b.x%p,(a.x*b.y+a.y)%p};
}
Node pow(Node a,long long b)
{
    Node ans=a;
    while(b)
    {
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
void solve()
{
    long long n,m;
    long long a,b,c,d;
    string tn,tm;
    cin>>tn>>tm;
    cin>>a>>b>>c>>d;
    w=p-1+(a==1);
    m=Change(tm,w);
    x=pow(Node{a,b},m>1?m-2:m-2+w);
    y=Node{c,d};
    z=y*x;
    w=p-1+(z.x==1);
    n=Change(tn,w);
    z=pow(z,n>1?n-2:n-2+w);
    x=x*z;
    cout<<(x.x+x.y)%p<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _;
    _=1;
//    cin>>_;
    while(_--)
    {
        solve();
    }
}

标签:游戏,最后,矩阵,一行,000,long,第一项
From: https://www.cnblogs.com/minz-io/p/17624191.html

相关文章

  • [圣诞大礼]Macintosh苹果机精品游戏合集
    开篇:很多人求MBP...求到MBP问题马上就来了,mac苹果机上软件已经很不错了,PS、office、AutoCAD都有,问题有什么好游戏呢?年终给大家很多MAC苹果机游戏希望大家喜欢啊。感谢ZOD骑士lv_1_ss分流游戏说明一点:下面的游戏全部都是MAC原生游戏,非MAC原生游戏不做收录。全部游戏都是来源于苹果商店,所以应该不需要......
  • 猜数字小游戏
    #include<stdio.h>#include<stdlib.h>#include<time.h>voidmenu()//主菜单{printf("---1.开始游戏--------0.退出游戏----\n");}voidgame(){//1.生成一个随机数intret=0;intguess=0;ret=rand()%100+1;//生成1-100之间的随机数,随机数区间可以......
  • 代码随笔-某游戏网站数据的爬取
    importrequestsimportparselimportcsvimportre#将表头写入CSV文件withopen('xxxgame.csv',mode='a',encoding='utf-8-sig',newline='')asf:csv_writer=csv.DictWriter(f,fieldnames=['title','nu......
  • 恒创科技:游戏选香港主机会卡吗?
    ​经常会有用户问道:做游戏服务器,使用香港主机会很卡吗?要知道,游戏运营最看重的就是用户体验,而游戏流畅不流畅要看所使用香港服务器本身的稳定性。因此,卡不卡,这样的形式提问是比较笼统的,您应该从应用场景里出发考虑,今天我们就一起来解析一下。做游戏选中国香港服务器有什......
  • python猜数字小游戏
    importrandomdefguess_number():  target_number=random.randint(1,100)  attempts=0  whileTrue:    guess=int(input("请输入一个1到100之间的整数:"))    attempts+=1    ifguess<target_number:      print("猜......
  • 剑指 Offer 12. 矩阵中的路径(中等)
    题目:classSolution{public:introw,col;booltraversal(vector<vector<char>>&board,stringword,inti,intj,intk){//传入棋盘,字符串,当前棋盘元素坐标,字符串索引if(i<0||i>=row||j<0||j>=col||board[i][j]!=word[k])retu......
  • 五子棋游戏
    #include<iostream>#include<iomanip>inth=16;intl=16;boolis_black=true;intall_list[16][16];boolblack_list[16][16];boolwhile_list[16][16];intx;inty;usingnamespacestd;voidf5(){ for(inti=0;i<=h;i++){ cout<<setw(......
  • 数字游戏
    P1043[NOIP2003普及组]数字游戏首先考虑链的情况怎么做。发现就是划分\(m\)次,直接考虑类似于乘积最大的DP,复杂度为\(O(n^2m)\)。对于环的情况,只需要暴力考虑\(n\)种破环的方式,所以总复杂度为\(O(n^3m)\)。注意取模和数组清空。code......
  • 取石子游戏(博弈dp)
    在研究过Nim游戏及各种变种之后,Orez又发现了一种全新的取石子游戏,这个游戏是这样的:有 n 堆石子,将这 n 堆石子摆成一排。游戏由两个人进行,两人轮流操作,每次操作者都可以从最左或最右的一堆中取出若干颗石子,可以将那一堆全部取掉,但不能不取,不能操作的人就输了。Orez......
  • Go面经 | 成都Go面试这么卷?卷王介绍:游戏行业 3年经验 20k+
    Go最新面经分享:算法、并发模型、缓存落盘、etcd、actor模型、epoll等等...本文先分享2段面经,文末总结了关键问题的复盘笔记。一定要看到最后!求职者情况分享一下好友的最新面经。简单说下这位好友的情况:坐标成都,游戏行业,3年开发经验,最近2年做Go语言开发,1年Java/PHP工作经验。......