NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 C. 兮陣

作者 主題: C. 兮陣  (閱讀 90 次)

oToToT

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
C. 兮陣
« 於: 三月 19, 2018, 02:31:22 pm »

Hash一下
代碼: [選擇]
#include <cstdio>
#include <cstdlib>
typedef long long lld;
const int N = 500000 + 1;
const lld q1 = 2147483587;
const lld p1 = 1208220623;
const lld q2 = 2147483647;
const lld p2 = 1000000007;

int main(){
int t; scanf("%d", &t);
while(t--){
int n, m; scanf("%d%d", &n, &m);
if(n == 1){
int ww;
for(int i=0;i<m;i++) scanf("%d", &ww);
puts("Yes"); continue;
}
if(m == 1){
int ww;
for(int i=0;i<n;i++) scanf("%d", &ww);
puts("Yes"); continue;
}
lld he1 = 1, me1 = 1, he2=1, me2=1;
bool ans = 1;
for(int i=0;i<m;i++){
int x;
scanf("%d", &x);
if(i==m-1) continue;
he1 = (he1 * p1 % q1 + x) % q1;
he2 = (he2 * p2 % q2 + x) % q2;
}
for(int i=1;i<n;i++){
lld meme1 = 1, meme2 = 1;
me1 = 1, me2 = 1;
for(int j=0;j<m;j++){
int x;
scanf("%d", &x);
if(j!=0){
meme1 = (meme1 * p1 % q1 + x) % q1;
meme2 = (meme2 * p2 % q2 + x) % q2;
}
if(j!=m-1){
me1 = (me1 * p1 % q1 + x) % q1;
me2 = (me2 * p2 % q2 + x) % q2;
}
}
ans &= ((meme1==he1) and (meme2==he2));
he1 = me1;
he2 = me2;
}
puts(ans?"Yes":"No");
}
return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 C. 兮陣