社区讨论

求助,样例过全WA

P4503[CTSC2014] 企鹅 QQ参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m388euqr
此快照首次捕获于
2024/11/08 12:23
去年
此快照最后确认于
2025/11/04 15:08
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e4+10,L=200;
const int mod1 = 114514, mod2 = 1919810;
const int p1 = 114, p2 = 191;  // p->????
char s[N][L];
int hsh1[N][L], hsh2[N][L], pw1[N], pw2[N], n,l,x,t[mod1+114],sum;
int gethash1(int x,int j, int i) { return (hsh1[x][i] - hsh1[x][j - 1] * pw1[i - j + 1] % mod1 + mod1) % mod1; }
//int gethash2(int j, int i) { return (hsh2[i] - hsh2[j - 1] * pw2[i - j + 1] % mod2 + mod2) % mod2; }
signed main() {
	cin>>n>>l>>x;
	pw1[0] = 1;
    pw2[0] = 1;
	for(int i=1;i<=n;i++){
		cin>>s[i]+1;
		for (int j = 1; j <= l; j++) {
			
	        hsh1[i][j] = (hsh1[i][j - 1] * p1 + s[i][j]) % mod1;
	        hsh2[i][j] = (hsh2[i][j - 1] * p2 + s[i][j]) % mod2;
	        if(i==1){
	        	pw1[j] = pw1[j - 1] * p1 % mod1;
			}
			//cout<<s[i][j]<<" "<<hsh1[i][j];
	    }
	    
	}
	
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=l;j++){
			//cout<<gethash1(i,1,j-1)<<" "<<gethash1(i,j+1,l)<<"\n";
    		int lr=(gethash1(i,1,j-1)*pw1[j-1]%mod1+gethash1(i,j+1,l)%mod1)%mod1;
    		//cout<<lr<<" "<<s[i][j]<<"\n";
    		t[lr]++;
		}
	}
	for(int i=1;i<=mod1+114;i++){
		if(t[i]>1)sum+=t[i]*(t[i]-1)/2;
	}
	cout<<sum;
    return 0;
}
rt

回复

0 条回复,欢迎继续交流。

正在加载回复...