P4503

思路:

注意到 $hash_i=hash_{i-1}*p+s_{i,j}$ 这个式子可以拆开。

$hash[1] = s[1]$ $hash[2] = s[1] * p + s[2]$ $hash[3] = (s[1] * p + s[2]) * p + s[3]$ $= s[1] * p^2 + s[2] * p + s[3]$

$hash_l=\sum_{i=1}^{j}s_i \times p ^{l-i}$ 所以在枚举字符覆盖时可以直接减去 $s_i$ 对 $Hash$ 的贡献。

哪里有问题?

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e4 + 10;
const int M = 2e2 + 10;
int n,l,S;
const int p = 131;
const int mod = 1e9 + 7;
int hash2[N],base[N];
char s[N][M];
int hash1[N];
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr),cout.tie(nullptr);
	scanf("%lld %lld %lld",&n,&l,&S);
	base[0] = 1;
	for(int i = 1;i <= l;i++){
		base[i] = base[i - 1] * p % mod;
		base[i] %= mod;
	}
	for(int i = 1;i <= n;i++){
		scanf("%s",s[i] + 1);
		for(int j = 1;j <= l;j++){
//			cout << s[i][j] << " " << (int)s[i][j] << " ";
			hash2[i] += s[i][j] * base[j];
			hash2[i] %= mod;
//			cout << hash2[i] << " " << base[j] << "\n";
			hash2[i] %= mod;
		}
	}
//	cout << endl;
	/*
	hash[1] = s[1]
	hash[2] = s[1] * p + s[2]
	hash[3] = (s[1] * p + s[2]) * p + s[3]
			= s[1] * p^2 + s[2] * p + s[3]
	How to delete one char 'j' of s?
	hash[len] - s[j] * p^{len-j}
	*/
	int ans = 0;
	for(int i = 1;i <= l;i++){
		for(int j = 1;j <= n;j++){
			hash1[j] = hash2[j] - s[j][i] * base[i] % mod;
//			cout << hash2[j] << " " << (int)s[j][i] << " " << base[i] << " " << hash1[j] << "--\n";
		}
		sort(hash1 + 1,hash1 + n + 1);
		int cnt = 1;
		for(int j = 1;j < n;j++){
//			cout << hash1[j] << " " << cnt << '\n';
			if(hash1[j] != hash1[j + 1]) cnt = 1;
			else{
				ans += cnt;cnt ++;
			}
		}
//		cout << endl;
	}
	printf("%lld",ans);
}