首页 > 其他分享 >【noip赛前20天冲刺集训 day3】矩阵挑战

【noip赛前20天冲刺集训 day3】矩阵挑战

时间:2023-10-12 09:03:18浏览次数:43  
标签:uint64 20 noip 交换 矩阵 day3 next leq seed

NOIP比赛前的冲刺训练 - 第3天:矩阵挑战

问题描述

您有一个 n×m 矩阵,行编号从 0n−1,列编号从 0m−1。最初,第i行第j列的元素是 i*m+j。系统支持三种类型的操作:

  1. 交换两行。
  2. 交换两列。
  3. 交换两个特定的元素。

任务是确定执行 q 次操作后矩阵的状态。

输入格式

为了最小化输入大小,问题使用以下输入方法:

  • 第一行包含四个整数 nmqseed,分别代表行数、列数、操作数和随机种子。

生成器代码如下:

```cpp
uint64_t seed;

uint64_t next() { // xorshift64
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}''

下一行是长度为 q 的字符串 s,表示每个操作的操作类型。
对于第i次操作,如果 si 是 'r',那么操作是交换 r1 和 r2 行。如果是 'c',那么交换 c1 和 c2 列。如果是 'f',那么交换元素 (r1,c1) 和 (r2,c2)。这些变量按顺序是调用 next() 后对 n 或 m 取模的返回值。

输出格式
为了最小化输出大小,设 ai,j 为最终矩阵第i行第j列的值。您只需要输出 \(\sum_{i,j} a_{i,j} \cdot 17^i \cdot 19^j\) mod 998244353 的值。

数据范围

对于100%的数据,条件如下:

  • (1 \(\leq\) n, m \(\leq\) 5000)
  • (1 \(\leq\) q \(\leq\) 10^6)
  • (0 \(\leq\) \(\text{seed}\) < 264)

后记 凯皇!!!

代码!@!@@!@!

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=1e6+5,mod=998244353;
int n,m,q,drx[N],dry[N],matrix[N][N],ans;
char s[M];
uint64_t seed;    

uint64_t next() { //xorshift64
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}
// 好像直接对pow取模不准,就手打一个MOD%

int main() {
    scanf("%d%d%d%llu%s",&n,&m,&q,&seed,s+1);
    for(int i=1;i<=n;i++){
        drx[i]=i;
        for(int j=1;j<=m;j++) matrix[i][j]=(i-1)*m+j-1;
    }
    for(int i=1;i<=m;i++) dry[i]=i;
    for(int i=1;i<=q;i++){
        if(s[i]=='r'){
            int x=next()%n+1,y=next()%n+1;
            swap(drx[x],drx[y]);
        }
        else if(s[i]=='c'){
            int x=next()%m+1,y=next()%m+1;
            swap(dry[x],dry[y]);
        }
        else{
            int x1=next()%n+1,y1=next()%m+1,x2=next()%n+1,y2=next()%m+1;
            swap(matrix[drx[x1]][dry[y1]],matrix[drx[x2]][dry[y2]]);
        }
    }
    for(int i=1,p1=1;i<=n;i++,p1=17ll*p1%mod)
        for(int j=1,p2=1;j<=m;j++,p2=19ll*p2%mod)
            ans=(ans+1ll*matrix[drx[i]][dry[j]]*p1%mod*p2)%mod;
    printf("%d\n",ans);
    
    return 0;
}

标签:uint64,20,noip,交换,矩阵,day3,next,leq,seed
From: https://www.cnblogs.com/Serein-KarBlog/p/17758652.html

相关文章

  • dhcp服务器迁移---从windows server 2003到windows server 2012
    近期,工作中接触到dhcp服务器的迁移。搜索了网上的一些解决方案,很详细。以下主要是碰到的一些问题以及解决方案。由于2003的版本太老,导出来的配置文件为古老的mdb格式,而导入到2012中的格式需要为txt。 在2003中,尝试用命令(网上可找到)导出来txt格式,但是公司那台服务器实现不了......
  • 【愚公系列】2023年10月 二十三种设计模式(十)-外观模式(Facade Pattern)
    ......
  • Spring Cloud 2023 新特性 同步网关
    网关不支持传统Servlet容器SpringCloudGateway需要运行在提供的Netty运行时。它不能在传统的Servlet容器中工作,也不能在构建为WAR时工作。WebFlux使用了异步非阻塞的编程模型,相较于传统的MVCServlet需要理解和适应新的编程范式和响应式编程概念,因此学习曲线可能......
  • 每日总结20231011
    代码时间(包括上课)3h代码量(行):100行博客数量(篇):1篇相关事项:1、今天是周三,今天上午上的是软件构造,软件构造讲的是程序规范化。2、今天下午我们进行了献血的演讲的观看,明白了献血的意义。3、今天还打算看看软件设计师相关的题目,我要过,我要通过,我要高分通过!......
  • 20231010
    //grant,privilege,reduction,lower,bestdiscount,cometothepoint,discountedprice,gointhehole,quantitydiscountgrant-授予,给予Tograntmeanstogiveorbestowsomethingtosomeone.Itinvolvesgivingpermission,approval,oraprivilegetoso......
  • 20231011
    //eclectic,extreme,halfway,medium,request,tradeoff,giveground,meanmethod,middleway,midwaypoint,strikeahappymediumeclectic-折中的,多元的Eclecticreferstoastyleorapproachthatcombineselementsorideasfromvarioussourcesorstyles.......
  • PE盘安装Windows Server 2022系统
    前言我需要一台稳定且能够全天候运行的机器时,电脑原本预装的Windows10系统,虽然在日常使用场景下表现良好,但大家都知道Windows系统的自动更新太频繁了,而且无法关闭。为了解决这个问题,我决定重新安装WindowsServer系统。这里我选择了WindowsServer2022版本。WindowsSer......
  • “储”类拔萃 | 天合储能荣获“2023年度中国新型储能系统集成商创新力奖”
    9月10日-11日,由中国化学与物理电源行业协会主办、100余家机构联办的碳中和能源高峰论坛暨第三届中国国际新型储能技术及工程应用大会在深圳圆满完成。天合储能受邀参会,荣获“2023年度中国新型储能系统集成商创新力奖”,同期天合光能董事长高纪凡作为光伏行业的引领者,致力于推动......
  • 120.
    注意到,对应原序列上\(a_i\)的选取过程,实际上是要求我们决策,并且从上个选取的地方进行转移的一个等效。那么问题变成了能否删除掉\([l,r]\)区间的所有数。首先一个必要条件即\(2\midlen\)并且,区间无严格众数,否则的话,即使我们每一步都能匹配成功,也只能匹配掉\(\lfloor{\d......
  • 20230921 做题记录
    20230921做题记录目录20230921做题记录总结1P2863[USACO06JAN]TheCowPromS2P2746[USACO5.3]校园网NetworkofSchools3P1407[国家集训队]稳定婚姻4P1072[NOIP2009提高组]Hankson的趣味题总结总计完成\(3+4\)题上午校内练习赛,下午改了上午的题,晚上继续......