NOIP比赛前的冲刺训练 - 第3天:矩阵挑战
问题描述
您有一个 n×m
矩阵,行编号从 0
到 n−1
,列编号从 0
到 m−1
。最初,第i行第j列的元素是 i*m+j
。系统支持三种类型的操作:
- 交换两行。
- 交换两列。
- 交换两个特定的元素。
任务是确定执行 q
次操作后矩阵的状态。
输入格式
为了最小化输入大小,问题使用以下输入方法:
- 第一行包含四个整数
n
、m
、q
和seed
,分别代表行数、列数、操作数和随机种子。
生成器代码如下:
```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