求助,样例过全WA
查看原帖
求助,样例过全WA
1113283
maziyue楼主2024/11/8 12:23
#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

2024/11/8 12:23
加载中...