?pid=4622
终于知道怎么hash解这题了，弱爆了==#
#include <cstdio>#include <cstdlib>#include <iostream>#include <cstring>#include <map>#include <string>#include <algorithm>#include <utility>#include <list>#include <fstream>#include <cctype>#include <vector>#include <cmath>#include <climits>#include <ctime>using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef unsigned UN;typedef pair<int, int> PAIR;typedef multimap<int, int> MMAP;typedef long double LF;const int MAXN(2010);const int MAXM(20010);const int MAXE(210);const int MAXK(6);const int HSIZE(3131);const int SIGMA_SIZE(40);const int MAXH(19);const int INFI((INT_MAX-1) >> 1);const ULL BASE(31);const LL LIM(1e13);const int INV(-10000);const int MOD(1000000007);const double EPS(1e-7);const LF PI(acos(-1.0));template<typename T> inline bool checkmax(T &a, T b){if(b > a) { a = b; return true;} return false;}template<typename T> inline bool checkmin(T &a, T b){if(b < a) { a = b; return true;} return false;}template<typename T> inline T ABS(T a){return a < 0? -a: a;}template<typename T> inline bool EZ(T a){return ABS(a) < EPS;}char str[MAXN];ULL hash[MAXN];ULL pow27[MAXN];ULL geth(int l, int r){return hash[l]-hash[r+1]*pow27[r-l+1];}struct HASH_MAP{int first[HSIZE];ULL sta[MAXN];int vl[MAXN], vr[MAXN], next[MAXN];int size;void init(){memset(first, -1, sizeof(first));size = 0;}bool insert(ULL ts, int tl, int tr, int &l, int &r){int h = ts%HSIZE;for(int i = first[h]; ~i; i = next[i])if(ts == sta[i]){l = vl[i];r = vr[i];vl[i] = tl;vr[i] = tr;return false;}sta[size] = ts;vl[size] = tl;vr[size] = tr;next[size] = first[h];first[h] = size++;return true;}} hm;int dp[2010][2010];int main(){pow27[0] = 1;for(int i = 1; i <= 2000; ++i) pow27[i] = pow27[i-1]*27;int TC;scanf("%d", &TC);while(TC–){scanf("%s", str);int len = strlen(str);memset(dp+1, 0, sizeof(dp[0])*len);hash[len] = 0;for(int i = len-1; i >= 0; –i) hash[i] = hash[i+1]*27+str[i]-‘a’+1;for(int i = 1;i <= len; ++i){int cnt = 0;hm.init();for(int j = 0; j <= len-i; ++j){int l, r;if(!hm.insert(geth(j, j+i-1), j, j+i-1, l, r)) dp[len-l][j+i] += -1;dp[len-j][j+i] += 1;}}for(int i = 1; i <= len; ++i){int ts = 0;for(int j = 1; j <= len; ++j){ts += dp[i][j];dp[i][j] = ts+dp[i-1][j];}}int Q;scanf("%d", &Q);while(Q–){int l, r;scanf("%d%d", &l, &r);printf("%d\n", dp[len-l+1][r]);}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，不要气馁于那前方的阴影，那只是因为我背后光芒万丈
