[关闭]
@jason-fan 2021-04-26T14:25:27.000000Z 字数 17027 阅读 178

哈希 Hash - 例题 AC CODE

CODE

BZOJ1567

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 55;
  5. const int mod = 1019260817;
  6. const int bs = 10007;
  7. int n, a[N][N], b[N][N];
  8. set<ll> vs[N];
  9. ll row[N][N], hsh[N][N][N], pw[N];
  10. ll calc(int c, int l, int r) {
  11.     return (row[c][r] - row[c][l - 1] * pw[r - l + 1] % mod + mod) % mod;
  12. }
  13. void inithash(int(*a)[N]) {
  14.     pw[0] = 1; for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * bs % mod;
  15.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) 
  16.         row[i][j] = ((ll)row[i][j - 1] * bs + a[i][j]) % mod;
  17.     for (int i = 1; i <= n; ++i) {
  18.         for (int j = 1; j <= n; ++j) { // (i,j)
  19.             for (int k = 1; max(i, j) + k - 1 <= n; ++k) {
  20.                 hsh[i][j][k] = 0;
  21.                 for (int p = 1; p <= k; ++p)
  22.                     hsh[i][j][k] = (hsh[i][j][k] * pw[k] + calc(i + p - 1, j, j + k - 1)) % mod;
  23.             }
  24.         }
  25.     }
  26. }
  27. int main() {
  28.     scanf("%d", &n);
  29.     for (int i = 1;i <= n;++i) for (int j = 1;j <= n;++j) scanf("%d", &a[i][j]);
  30.     for (int i = 1;i <= n;++i) for (int j = 1;j <= n;++j) scanf("%d", &b[i][j]);
  32.     inithash(a);
  33.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
  34.         for (int k = 1; min(i, j) + k - 1 <= n; ++k) vs[k].insert(hsh[i][j][k]);
  35.     inithash(b);
  36.     for (int k = n; k >= 1; --k)
  37.         for (int i = 1; i + k - 1 <= n; ++i)
  38.             for (int j = 1; j + k - 1 <= n; ++j) if (vs[k].count(hsh[i][j][k]))
  39.                 {printf("%d\n", k); return 0;}
  40.     puts("0");
  41.     return 0;
  42. }

BZOJ4337

  1. #include <bits/stdc++.h>
  2. template<typename _Tp>
  3. inline void red(_Tp& x) {
  4.     x = 0;bool fg = 0;char ch = getchar();
  5.     while (ch < '0' || ch>'9') { if (ch == '-') fg ^= 1;ch = getchar(); }
  6.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  7.     if (fg) x = -x;
  8. }
  9. template <typename _Tp, typename... Args>void red(_Tp& t, Args &... args) { red(t);red(args...); }
  10. using namespace std;
  11. typedef long long ll;
  12. const int mod = 1019260817;
  13. const int N = 110;
  14. const int base = 97;
  15. int head[N], fa[N], pnt[N], nxt[N], E;
  16. int m, n, siz[N], rt1, rt2;
  17. ll hah[N], pw[N];
  18. pair<ll, ll> Hash[N];
  19. vector<int> e[N];
  20. void init() {
  21.     for (int i = 1;i <= n;++i) e[i].clear();
  22.     rt1 = rt2 = -1;
  23. }
  24. void dfs(int u, int f = 0, int dep = 1) {
  25.     siz[u] = 1; hah[u] = dep;
  26.     for (int i = 0, v;i < e[u].size();++i) {
  27.         v = e[u][i]; if (v == f) continue;
  28.         dfs(v, u, dep + 1);
  29.         siz[u] += siz[v];
  30.     }
  31.     sort(e[u].begin(), e[u].end(), [](int x, int y) {
  32.         return hah[x] < hah[y];
  33.         });
  34.     for (int i = 0, v;i < e[u].size();++i) {
  35.         v = e[u][i]; if (v == f) continue;
  36.         hah[u] = (hah[u] * pw[siz[v]] + hah[v]) % mod;
  37.     }
  38. }
  39. void getroot(int u, int f = 0) {
  40.     assert(u != 0);
  41.     siz[u] = 1; int mxsiz = 0;
  42.     for (int i = 0, v;i < e[u].size();++i) {
  43.         v = e[u][i]; if (v == f) continue;
  44.         getroot(v, u); siz[u] += siz[v];
  45.         mxsiz = max(mxsiz, siz[v]);
  46.     }
  47.     mxsiz = max(mxsiz, n - siz[u]);
  48.     if (mxsiz <= n / 2) {
  49.         if (rt1 == -1) rt1 = u;
  50.         else rt2 = u;
  51.     }
  52. }
  54. int main() {
  55.     red(m);
  56.     pw[0] = 1; for (int i = 1;i < N;++i) pw[i] = pw[i - 1] * base % mod;
  57.     for (int t = 1;t <= m;++t) {
  58.         init(); red(n);
  59.         for (int i = 1;i <= n;++i) {
  60.             red(fa[i]);
  61.             if (fa[i] != 0) {
  62.                 e[fa[i]].push_back(i);
  63.                 e[i].push_back(fa[i]);
  64.             }
  65.         }
  66.         getroot(1);
  67.         dfs(rt1); Hash[t].first = hah[rt1];
  68.         if (rt2 == -1) Hash[t].second = hah[rt1];
  69.         else {
  70.             dfs(rt2); Hash[t].second = hah[rt2];
  71.             if (Hash[t].first > Hash[t].second)
  72.                 swap(Hash[t].first, Hash[t].second);
  73.         }
  74.     }
  75.     for (int t = 1;t <= m;++t) {
  76.         for (int i = 1;i <= m;++i) {
  77.             if (Hash[t] == Hash[i]) {
  78.                 printf("%d\n", i);
  79.                 break;
  80.             }
  81.         }
  82.     }
  83.     return 0;
  84. }

SPOJ-LCS2 luogu

  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<ll, ll> pll;
  7. typedef unsigned long long ull;
  8. const int N = 100010;
  10. namespace strhash {
  11.     const int p1 = 1019260817;
  12.     const int p2 = 1019260819;
  13.     const int bs = 233;
  14.     pll pw[N], f[N];
  15.     pll operator*(pll a, ll b) { return pll(a.fi * b % p1, a.se * b % p2); }
  16.     pll operator+(pll a, ll b) { return pll((a.fi + b) % p1, (a.se + b) % p2); }
  17.     pll operator-(pll a, pll b) { return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2); }
  18.     pll operator*(pll a, pll b) { return pll(a.fi * b.fi % p1, a.se * b.se % p2); }
  19.     void init(char* S, int n) {
  20.         pw[0] = pll{ 1,1 };
  21.         for (int i = 1;i <= n;++i) {
  22.             f[i] = (f[i - 1] * bs + (S[i] - 'a' + 1));
  23.             pw[i] = pw[i - 1] * bs;
  24.         }
  25.     }
  26.     ull gethash(int l, int r) {
  27.         pll a = f[r] - f[l - 1] * pw[r - l + 1];
  28.         return (ull)a.fi << 32 | (ull)a.se;
  29.     }
  30. }
  31. using strhash::init;using strhash::gethash;
  32. int n, len[10];
  33. char str[10][N];
  34. struct my_hash {
  35.     static ull mix64(ull x) {
  36.         x += 0x9e3779b97f4a7c15;
  37.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  38.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  39.         return x ^ (x >> 31);
  40.     }
  41.     size_t operator()(ull x) const { return mix64(x); }
  42. };
  43. unordered_set<ull, my_hash> S1, S2;
  44. bool check(int l) {
  45.     init(str[0], len[0]);
  46.     S1.clear();S2.clear();
  47.     for (int i = 1;i + l - 1 <= len[0];++i) {
  48.         S1.insert(gethash(i, i + l - 1));
  49.     }
  50.     for (int i = 1;i < n;++i) {
  51.         if (S1.empty()) return false;
  52.         init(str[i], len[i]);
  53.         for (int j = 1;j + l - 1 <= len[i];++j) {
  54.             ull mask = gethash(j, j + l - 1);
  55.             if (S1.find(mask) != S1.end()) {
  56.                 S2.insert(mask);
  57.                 S1.erase(mask);
  58.             }
  59.         }
  60.         S1.clear();swap(S1, S2);
  61.     }
  62.     return !S1.empty();
  63. }
  64. int main() {
  65.     while (scanf("%s", str[n] + 1) != EOF) {
  66.         len[n] = strlen(str[n] + 1);
  67.         ++n;
  68.     }
  69.     int L = 0, R = *min_element(len, len + n), M, ans;
  70.     while (L <= R) {
  71.         M = (L + R) >> 1;
  72.         if (check(M)) ans = M, L = M + 1;
  73.         else R = M - 1;
  74.     }
  75.     cout << ans << endl;
  76.     return 0;
  77. }

BZOJ3198

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 100010;
  5. const int p1 = 1019260817;
  6. const int p2 = 1019260819;
  7. const int bs = 125641;
  8. int a[N][6], n, k, C[7][7];
  9. struct Hash_map {
  10.     static const int MAX_SIZE = 200010, M = 1627361;
  11.     struct data {
  12.         int nxt;
  13.         ll key, value;
  14.     } e[MAX_SIZE];
  15.     int head[M], size;
  16.     inline int f(ll key) { return key % M; } // 哈希函数
  17.     ll& operator[](const ll& key) {
  18.         int ky = f(key);
  19.         for (int i = head[ky]; i != -1; i = e[i].nxt)
  20.             if (e[i].key == key) return e[i].value;
  21.         return e[++size] = data{ head[ky], key, 0 }, head[ky] = size, e[size].value;
  22.     }
  23.     void clear() {
  24.         memset(head, -1, sizeof(head));
  25.         size = 0;
  26.     }
  27.     Hash_map() { clear(); }
  28. };
  29. Hash_map ct;
  30. ll calc(int mask) {
  31.     ct.clear(); ll res = 0;
  32.     for (int i = 1;i <= n;++i) {
  33.         ll h1 = 0, h2 = 0;
  34.         for (int p = 0;p < 6;++p) if ((mask >> p) & 1) {
  35.             h1 = (h1 * bs + a[i][p]) % p1;
  36.             h2 = (h2 * bs + a[i][p]) % p2;
  37.         }
  38.         res += ct[h1 * h2]++;
  39.     }
  40.     return res;
  41. }
  42. int main() {
  43.     scanf("%d%d", &n, &k);
  44.     for (int i = 1;i <= n;++i) for (int j = 0;j < 6;++j) scanf("%d", &a[i][j]);
  45.     C[0][0] = 1;
  46.     for (int i = 1;i <= 6;++i) {
  47.         C[i][0] = 1;
  48.         for (int j = 1;j <= i;++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  49.     }
  50.     ll ans = 0;
  51.     for (int mask = 0;mask < (1 << 6);++mask) {
  52.         int ct = 0; for (int x = mask;x;x -= x & -x) ++ct;
  53.         if (ct < k) continue;
  54.         ll tmp = calc(mask) * C[ct][k];
  55.         if ((ct - k) & 1) ans -= tmp;
  56.         else ans += tmp;
  57.     }
  58.     printf("%lld\n", ans);
  59.     return 0;
  60. }

HDU6647 vjudge

  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. typedef long long ll;
  6. const int N = 100010;
  7. const int mod = 998244353;
  8. inline ll Mod(ll x) {return x < mod ? x : x % mod;}
  10. typedef pair<ll, ll> pll;
  11. const int p1 = 1019260817; // 双模 hash 
  12. const int p2 = 1019260819;
  13. const int c = 517666;
  14. pll operator*(const pll &a, const ll &b) {return pll(a.fi * b % p1, a.se * b % p2);}
  15. pll operator*(const pll &a, const pll &b) {return pll(a.fi * b.fi % p1, a.se * b.se % p2);}
  16. pll operator+(const pll &a, const ll &b) {return pll((a.fi + b) % p1, (a.se + b) % p2);}
  17. pll operator-(const pll &a, const pll &b) {return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2);}
  18. pll operator+(const pll &a, const pll &b) {return pll((a.fi + b.fi) % p1, (a.se + b.se) % p2);}
  20. ll fac[N], ifac[N], inv[N], pr[N];
  21. bool v[2000000];int tot;
  22. void init(int n) {
  23.     fac[0] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  24.     for (int i = 1; i <= n; ++i) fac[i] = Mod(fac[i - 1] * i);
  25.     for (int i = 2; i <= n; ++i) inv[i] = Mod((mod - mod / i) * inv[mod % i]);
  26.     for (int i = 2; i <= n; ++i) ifac[i] = Mod(inv[i] * ifac[i - 1]);
  27.     for (int i = 2; tot < n; ++i) {
  28.         if(!v[i]) pr[++tot] = i;
  29.         for (int j = 1; j <= tot && pr[j] * i < 2e6; ++j) {
  30.             v[i * pr[j]] = 1;
  31.             if(i % pr[j] == 0) break;
  32.         }
  33.     }
  34.     srand(time(0));
  35.     random_shuffle(pr + 1, pr + tot + 1);
  36. }
  37. vector<int> e[N];
  38. int t, n, siz[N];
  39. ll f[N], g[N]; // f[u]: (以 1 为根)遍历 u 子树本质不同括号序列方案数 ； g[u] 以 u 为根
  40. pll fh[N], gh[N]; // fh[u]: (以 1 为根) u 子树哈希值 ； gh[u] 以 u 为根
  41. map<pll, int> ct[N]; // 统计 u 子树某哈希值出现次数
  43. ll qpow(ll a, ll b = mod - 2) {
  44.     ll r = 1;
  45.     for ( ; b; b>>=1, a = Mod(a * a)) if(b & 1) r = Mod(r * a);
  46.     return r;
  47. }
  49. void dfs1(int u, int fa) {
  50.     ct[u].clear();
  51.     f[u] = fac[e[u].size() - (u != 1)];
  52.     fh[u] = pll(0, 0); siz[u] = 1;
  53.     for(auto &&v : e[u]) if(v != fa) {
  54.         dfs1(v, u);
  55.         fh[u] = fh[u] + fh[v] * pr[siz[v]];
  56.         f[u] = Mod(f[u] * f[v]);
  57.         siz[u] += siz[v];
  58.     }
  59.     sort(e[u].begin(), e[u].end(), [](int x, int y) {return fh[x] < fh[y];});
  60.     pll pre(-1, -1); int cnt = 0;
  61.     for(auto &&v : e[u]) if(v != fa) {
  62.         if(pre == fh[v]) f[u] = Mod(f[u] * inv[++cnt]);
  63.         else {
  64.             if(pre.fi != -1) ct[u][pre] = cnt;
  65.             cnt = 1, pre = fh[v];
  66.         }
  67.     }
  68.     if(pre.fi != -1) ct[u][pre] = cnt;
  69.     fh[u] = fh[u] + c; 
  70. }
  72. void dfs2(int u, int fa, pll cur, ll now) {
  73.     // 换根DP ： cur 为父亲方向哈希值， now 为父亲方向 f
  74.     g[u] = Mod(f[u] * now);
  75.     gh[u] = fh[u] + cur * pr[n - siz[u]];
  76.     if(u != 1) {
  77.         g[u] = Mod(Mod(g[u] * e[u].size()));
  78.         g[u] = Mod(g[u] * inv[++ct[u][cur]]);
  79.     } 
  80.     for(auto &&v : e[u]) if(v != fa) {
  81.         pll _cur = fh[u] - fh[v] * pr[siz[v]] + cur * pr[n - siz[u]];
  82.         ll _now = Mod(Mod(g[u] * inv[e[u].size()]) * qpow(f[v]));
  83.         _now = Mod(_now * ct[u][fh[v]]);
  84.         dfs2(v, u, _cur, _now);
  85.     }
  86. }
  88. void rmain() {
  89.     scanf("%d", &n);
  90.     for (int i = 1; i <= n; ++i) e[i].clear();
  91.     for (int i = 1; i < n; ++i) {
  92.         int u, v; scanf("%d%d", &u, &v);
  93.         e[u].push_back(v); e[v].push_back(u);
  94.     }
  95.     dfs1(1, 0);
  96.     dfs2(1, 0, pll(0, 0), 1);
  97.     ct[0].clear();
  98.     ll ans = 0;
  99.     for (int i = 1; i <= n; ++i) {
  100.         if(ct[0].count(gh[i])) continue;
  101.         ct[0][gh[i]] = 1;
  102.         ans = Mod(ans + g[i]);
  103.     }
  104.     printf("%lld\n",ans);
  105. }
  106. int main() {
  107.     init(N - 1);   
  108.     scanf("%d", &t);
  109.     while(t--) rmain();
  110.     return 0;
  111. }

51Nod1553 vjudge

  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define ls (x<<1)
  5. #define rs (x<<1|1)
  6. #define mid ((l+r)>>1)
  8. using namespace std;
  9. const int N = 100010;
  10. int n,m,q; char s[N];
  12. typedef long long ll;
  13. typedef pair<ll,ll> pll;
  14. const int p1 = 1019260817; // 双模 hash 
  15. const int p2 = 1019260819;
  16. const int bs = 125641; // 基数
  17. pll operator*(const pll &a,const ll &b) {return pll(a.fi * b % p1, a.se * b % p2);}
  18. pll operator*(const pll &a,const pll &b) {return pll(a.fi * b.fi % p1, a.se * b.se % p2);}
  19. pll operator+(const pll &a,const ll &b) {return pll((a.fi + b) % p1, (a.se + b) % p2);}
  20. pll operator-(const pll &a,const pll &b) {return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2);}
  21. pll operator+(const pll &a,const pll &b) {return pll((a.fi + b.fi) % p1, (a.se + b.se) % p2);}
  22. pll pw[N],pws[N]; // pw[i] = bs ^ i
  24. void init(int n) {
  25.     pw[0] = {0, 0};
  26.     for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * bs;
  27. }
  28. struct dat {
  29.     pll f; // 哈希值
  30.     int len; // 串长
  31.     dat() { f = {0, 0}; len = 0; }
  32.     dat(const pll &_f,const int &_len) { f = _f; len = _len; }
  33. };
  34. dat operator*(const dat &a,const dat &b) {
  35.     return dat(a.f * pw[b.len] + b.f, a.len + b.len);
  36. }
  39. dat D[N<<2]; int tag[N<<2];
  41. ostream &operator<<(ostream &out,const dat &a) {
  42.     return out<<"("<<a.f.first<<", "<<a.f.second<<", l="<<a.len<<") ";
  43. }
  45. void pushup(int x) {D[x]=D[ls]*D[rs];}
  46. void build(int l=1,int r=n,int x=1) {
  47.     tag[x]=-1;
  48.     if(l==r) {D[x]=dat({s[l]-'0',s[l]-'0'},1);return ;}
  49.     build(l,mid,ls);build(mid+1,r,rs);
  50.     pushup(x);
  51. }
  52. void seteq(int x,int vl) { tag[x]=vl; D[x].f=pws[D[x].len-1]*vl; }
  53. void pushdown(int x) {
  54.     if(tag[x]!=-1) {
  55.         seteq(ls,tag[x]); seteq(rs,tag[x]);
  56.         tag[x]=-1;
  57.     }
  58. }
  59. void modify(int L,int R,int vl,int l=1,int r=n,int x=1) {
  60.     if(L<=l&&r<=R) return seteq(x,vl);
  61.     pushdown(x);
  62.     if(L<=mid) modify(L,R,vl,l,mid,ls);
  63.     if(R>mid) modify(L,R,vl,mid+1,r,rs);
  64.     pushup(x);
  65. }
  66. dat query(int L,int R,int l=1,int r=n,int x=1) {
  67.     if(L>R) return dat();
  68.     if(L<=l&&r<=R) return D[x];
  69.     pushdown(x); dat ret;
  70.     if(L<=mid) ret=query(L,R,l,mid,ls);
  71.     if(R>mid) ret=ret*query(L,R,mid+1,r,rs);
  72.     return ret;
  73. }
  74. int main() {
  75.     scanf("%d%d%d",&n,&m,&q);q+=m;
  76.     scanf("%s",s+1);
  77.     pws[0]=pw[0]={1,1};
  78.     for(int i=1;i<=n;++i) {
  79.         pw[i]=pw[i-1]*bs;
  80.         pws[i]=pws[i-1]+pw[i];
  81.     }
  82.     build();
  83.     while(q--) {
  84.         int op,l,r,x;
  85.         scanf("%d%d%d%d",&op,&l,&r,&x);
  86.         if(op==1) {
  87.             modify(l,r,x);
  88.         }else {
  89.             dat a=query(l+x,r),b=query(l,r-x);
  90.             // printf("[%d,%d] [%d,%d]\n",l+x,r,l,r-x);
  91.             // cerr<<a<<" "<<b<<endl;
  92.             if(a.f==b.f) puts("YES");
  93.             else puts("NO");
  94.         }
  95.     }
  96.     return 0;
  97. }

51Nod1863 vjudge

  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. template<typename _Tp>
  5. inline void read(_Tp& x) {
  6.     x = 0;bool fg = 0;char ch = getchar();
  7.     while (ch < '0' || ch>'9') { if (ch == '-') fg ^= 1;ch = getchar(); }
  8.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  9.     if (fg) x = -x;
  10. }
  11. template<typename _Tp, typename... Args>void read(_Tp& t, Args &... args) { read(t);read(args...); }
  12. using namespace std;
  13. typedef long long ll;
  14. const int N = 100010;
  15. const int M = 500010;
  16. int head[N], pnt[M << 1], nxt[M << 1], E;
  17. int n, m, P[N], PP[N], w[N];
  18. void adde(int u, int v) {
  19.     E++;pnt[E] = v;nxt[E] = head[u];head[u] = E;
  20. }
  21. namespace seq_Hash {
  22.     typedef long long ll;
  23.     typedef pair<ll, ll> pll;
  24.     const int p1 = 1019260817;
  25.     const int p2 = 1019260819;
  26.     const int bs = 10007;
  27.     pll operator*(const pll& a, const ll& b) { return pll(a.fi * b % p1, a.se * b % p2); }
  28.     pll operator*(const pll& a, const pll& b) { return pll(a.fi * b.fi % p1, a.se * b.se % p2); }
  29.     pll operator+(const pll& a, const ll& b) { return pll((a.fi + b) % p1, (a.se + b) % p2); }
  30.     pll operator-(const pll& a, const pll& b) { return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2); }
  31.     pll operator+(const pll& a, const pll& b) { return pll((a.fi + b.fi) % p1, (a.se + b.se) % p2); }
  32.     pll pw[N];
  33.     void init(int n) {
  34.         pw[0] = { 1, 1 };
  35.         for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * bs;
  36.     }
  37.     struct dat {
  38.         pll f; int len;
  39.         dat() { f = { 0,0 };len = 0; }
  40.         dat(const pll& _f, const int& _len) { f = _f; len = _len; }
  41.     };
  42.     dat operator*(const dat& a, const dat& b) {
  43.         return dat(a.f * pw[b.len] + b.f, a.len + b.len);
  44.     }
  45.     ostream& operator<<(ostream& out, const dat& a) {
  46.         return out << "dat{ (" << a.f.first << ", " << a.f.second << "), l=" << a.len << " } ";
  47.     }
  48. }using namespace seq_Hash;
  50. namespace segt {
  51. #define ls(p) t[p].l
  52. #define rs(p) t[p].r
  53. #define mid ((l+r)>>1)
  54.     struct node {
  55.         int l, r; dat d;
  56.     }t[N * 30];
  57.     int sz, root;
  58.     int newnode() { ++sz;t[sz] = { 0,0,dat() }; return sz; }
  59.     void pushup(int p) { t[p].d = t[ls(p)].d * t[rs(p)].d; }
  60.     void modify(int p, int& q, int ps, int l = 1, int r = n) {
  61.         if (!q) q = newnode();
  62.         if (l == r) { t[q].d.f = t[p].d.f + 1;t[q].d.len = 1;return; }
  63.         if (ps <= mid) modify(ls(p), ls(q), ps, l, mid), rs(q) = rs(p);
  64.         else modify(rs(p), rs(q), ps, mid + 1, r), ls(q) = ls(p);
  65.         pushup(q);
  66.         assert(t[p].d.len == r - l + 1);
  67.         assert(t[q].d.len == r - l + 1);
  68.     }
  69.     void build(int& p, int l = 1, int r = n) {
  70.         p = newnode();
  71.         if (l == r) { t[p].d.len = 1;t[p].d.f = pll(0, 0);return; }
  72.         build(ls(p), l, mid); build(rs(p), mid + 1, r);
  73.         pushup(p);
  74.         assert(t[p].d.len == r - l + 1);
  76.     }
  77.     void print(int p, int l = 1, int r = n) {
  78.         if (l == r) {
  79.             assert(t[p].d.f.first == t[p].d.f.second);
  80.             for (int i = 0;i < t[p].d.f.first;++i) printf("%d ", P[l]);
  81.             return;
  82.         }
  83.         print(ls(p), l, mid); print(rs(p), mid + 1, r);
  84.     }
  85.     int cmp(int p, int q, int ps = n + 1, int l = 1, int r = n, bool fg = 0) {
  86.         if (q == 0) return -1;
  87.         if (l == r) {
  88.             ll v = t[p].d.f.fi + (ll)(ps == l) - t[q].d.f.fi;
  89.             if (v == 0) return 0;
  90.             return (v < 0) ? -1 : 1;
  91.         }
  92.         pll _p = t[ls(p)].d.f + ((l <= ps && ps <= mid) ? (pw[mid - ps]) : (pll{ 0,0 }));
  93.         pll _q = t[ls(q)].d.f;
  94.         if (_p == _q) return cmp(rs(p), rs(q), ps, mid + 1, r, fg);
  95.         return cmp(ls(p), ls(q), ps, l, mid, fg);
  96.     }
  97. }
  99. struct pp { int u, id; };
  100. bool operator<(const pp a, const pp b) {
  101.     int t = segt::cmp(a.id, b.id);
  102.     return (t == 0) ? (a.id < b.id) : (t < 0);
  103. }
  104. bool operator>(const pp a, const pp b) { return b < a; }
  106. pp dis[N];
  107. bool vis[N]; int pre[N];
  108. void dij() {
  109.     set<pp> Q;
  110.     segt::build(segt::root);
  111.     dis[1] = pp{ 1,0 };
  112.     segt::modify(segt::root, dis[1].id, w[1]);
  113.     Q.insert(dis[1]);
  114.     while (!Q.empty()) {
  115.         int u = Q.begin()->u;Q.erase(Q.begin());
  116.         if (vis[u]) continue;
  117.         vis[u] = 1;
  118.         if (u == n) break;
  119.         for (int i = head[u];i;i = nxt[i]) {
  120.             int v = pnt[i]; if (vis[v]) continue;
  121.             if (segt::cmp(dis[u].id, dis[v].id, w[v]) < 0) {
  122.                 auto it = Q.find(dis[v]);
  123.                 if (it != Q.end()) Q.erase(it);
  124.                 dis[v].u = v;dis[v].id = 0;
  125.                 segt::modify(dis[u].id, dis[v].id, w[v]);
  126.                 Q.insert(dis[v]);
  127.                 pre[v] = u;
  128.             }
  129.         }
  130.     }
  131. }
  133. int main() {
  134.     read(n, m); init(n);
  135.     for (int i = 1;i <= n;++i) read(P[i]), PP[P[i]] = i;
  136.     for (int i = 1;i <= n;++i) read(w[i]), w[i] = PP[w[i]];
  137.     for (int i = 1;i <= m;++i) {
  138.         int u, v;read(u, v);
  139.         adde(u, v);adde(v, u);
  140.     }
  141.     dij();
  142.     segt::print(dis[n].id);
  143.     puts("");
  144.     return 0;
  145. }

XJOI4588

备用链接1 备用链接2

  1. #pragma GCC optimize(2)
  2. #pragma GCC optimize(3)
  3. #include <bits/stdc++.h>
  4. #define fi first
  5. #define se second
  6. using namespace std;
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9. typedef pair<ll, ll> pll;
  10. const int N = 1000010;
  11. const int mod = 998244353;
  12. const int p1 = 1e9 + 7;
  13. const int p2 = 1e9 + 9;
  14. const int base = 433;
  15. template<size_t SIZE>
  16. struct hashmap {
  17.     static const int MOD = (1 << 21);
  18.     int head[MOD], nxt[SIZE], st[SIZE], top, E;
  19.     ull key[SIZE];
  20.     inline int find(ull _key) {
  21.         int hah = _key & (MOD - 1);
  22.         for (int i = head[hah];i;i = nxt[i]) {
  23.             if (_key == key[i]) return i;
  24.         }
  25.         return -1;
  26.     }
  27.     inline int insert(ull _key) {
  28.         int hah = _key & (MOD - 1);
  29.         if (head[hah] == 0) st[++top] = hah;
  30.         E++;key[E] = _key;nxt[E] = head[hah];head[hah] = E;
  31.         return E;
  32.     }
  33.     inline void clear() {
  34.         while (top) head[st[top--]] = 0;E = 0;
  35.     }
  36. };
  37. hashmap<N * 2> vs, mp;
  38. ll fpow(ll a, ll b) { ll r = 1;for (;b;b >>= 1, a = (a * a) % mod) r = (r * a) % mod;return r; }
  39. ll inv[N], fac[N];ull pww[N << 1];
  40. pll pw[N], hah[N];
  41. char s[N];int n;
  42. pll operator*(const pll a, const ll b) { return pll(a.fi * b % p1, a.se * b % p2); }
  43. pll operator*(const pll a, const pll b) { return pll(a.fi * b.fi % p1, a.se * b.se % p2); }
  44. pll operator+(const pll a, const ll b) { return pll((a.fi + b) % p1, (a.se + b) % p2); }
  45. pll operator-(const pll a, const pll b) { return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2); }
  46. void print(pll a) { printf("(%lld,%lld)\n", a.fi, a.se); }
  47. pll gethash(int l, int r) { return hah[r] - (hah[l - 1] * pw[r - l + 1]); }
  48. void init() {
  49.     pw[0] = pll(1ll, 1ll);
  50.     for (int i = 1;i <= n;i++) {
  51.         pw[i] = pw[i - 1] * (ll)base;
  52.         hah[i] = hah[i - 1] * (ll)base + (ll)(s[i] - 'a' + 1);
  53.     }
  54.     fac[0] = fac[1] = inv[0] = inv[1] = 1;
  55.     for (int i = 2;i <= n;i++) {
  56.         fac[i] = fac[i - 1] * i % mod;
  57.         inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  58.     }
  59.     pww[0] = { 1ull };
  60.     for (int i = 1;i <= 2 * n;i++) pww[i] = pww[i - 1] * 557ull;
  61. }
  62. ull tomask(pll a) {
  63.     ull x = (ull)a.fi << 32 | (ull)a.se;
  64.     x ^= x << 14;x ^= x >> 16;x ^= x << 7;
  65.     return x ^ 1919810;
  66. }
  67. int cnt[N << 1], id[N << 1];
  68. int main() {
  69.     scanf("%s", s + 1);
  70.     n = strlen(s + 1);
  71.     init();
  72.     ll ress = 0;
  73.     for (int d = 1;d <= n;d++) {
  74.         int t = n / d, rs = n % d;
  75.         vs.clear();mp.clear();
  76.         ll ans = fac[t], res = 0;ull mask = 0;
  77.         for (int i = 1;i <= t;i++) {
  78.             // (i-1)*d+1 ~ i*d
  79.             ull tmp = tomask(gethash((i - 1) * d + 1, i * d));
  80.             int p = mp.find(tmp);
  81.             if (p == -1) {
  82.                 cnt[p = mp.insert(tmp)] = 1;
  83.             }
  84.             else {
  85.                 cnt[p]++;ans = (ans * inv[cnt[p]]) % mod;
  86.             }
  87.             id[i * 2 - 1] = p; mask += pww[p];
  88.             tmp = tomask(gethash((i - 1) * d + 1 + rs, i * d + rs));
  89.             p = mp.find(tmp);
  90.             if (p == -1) { p = mp.insert(tmp);cnt[p] = 0; }
  91.             id[i * 2] = p;
  92.         }
  94.         res = (res + ans) % mod;
  95.         vs.insert(mask);
  96.         if (rs) {
  97.             for (int i = t;i >= 1;i--) {
  98.                 ans = (ans * cnt[id[i * 2 - 1]]) % mod;
  99.                 cnt[id[i * 2 - 1]]--;
  100.                 mask -= pww[id[i * 2 - 1]];
  101.                 ans = (ans * inv[++cnt[id[i * 2]]]) % mod;
  102.                 mask += pww[id[i * 2]];
  103.                 if (vs.find(mask) != -1) continue;
  104.                 vs.insert(mask);
  105.                 res = (res + ans) % mod;
  106.             }
  107.         }
  108.         ress = (ress + res) % mod;
  109.     }
  110.     printf("%lld\n", ress);
  111.     return 0;
  112. }

UOJ522

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. #define LL long long
  5. #define pii pair<int, int>
  7. const int maxN = 1005, mod = 1472172389;
  9. mt19937 rnd( time(NULL) );
  11. int h[maxN + 1][26];
  12. char ans[maxN + 1];
  14. inline void update(int &x, int y) { x = (LL)x + y >= mod ? (LL)x + y - mod : (LL)x + y; }
  16. struct Graph
  17. {
  18.     int n, m, cnt;
  19.     int res[maxN + 1], tp[maxN + 1];
  20.     int f[maxN + 1][maxN + 1];
  22.     vector<pii> to[maxN + 1];
  24.     void init()
  25.     {
  26.         scanf("%d %d", &n, &m);
  27.         for(int i = 1; i <= m; i++)
  28.         {
  29.             int x, y;
  30.             char c[2];
  31.             scanf("%d %d %s", &x, &y, c);
  32.             to[x].push_back( pii(y, c[0] - 'a') );
  33.         }
  34.         for(int i = 1; i <= n; i++) f[0][i] = res[i] = 1;
  35.     }
  37.     int calc()
  38.     {
  39.         cnt ++;
  40.         int sum = 0;
  41.         for(int u = 1; u <= n; u++)
  42.         {
  43.             int res = 0;
  44.             for(int i = 0; i < to[u].size(); i++)
  45.             {
  46.                 int v = to[u][i].first, c = to[u][i].second;
  47.                 update(res, 1ll * h[cnt][c] * f[cnt - 1][v] % mod);
  48.             }
  49.             update(sum, f[cnt][u] = res);
  50.         }
  51.         return sum;
  52.     }
  54.     int get(int nc)
  55.     {
  56.         for(int i = 1; i <= n; i++) tp[i] = 0;
  57.         int sum = 0;
  58.         for(int u = 1; u <= n; u++)
  59.             for(int i = 0; i < to[u].size(); i++)
  60.             {
  61.                 int v = to[u][i].first, c = to[u][i].second;
  62.                 if(c != nc) continue;
  63.                 int t = 1ll * res[u] * h[cnt][c] % mod;
  64.                 update(tp[v], t);
  65.                 update(sum, 1ll * t * f[cnt - 1][v] % mod); 
  66.             }
  67.         return sum;
  68.     }
  70.     void upd()
  71.     {
  72.         for(int i = 1; i <= n; i++) res[i] = tp[i];
  73.         cnt --;
  74.     }
  75. }G1, G2;
  77. int main()
  78. {
  79.     for(int i = 1; i <= 1001; i++)
  80.         for(int c = 0; c < 26; c++) 
  81.             h[i][c] = rnd() % (mod - 1) + 1;
  83.     G1.init(); G2.init();
  84.     for(int i = 1; i <= 1001; i++)
  85.         if(G1.calc() != G2.calc())
  86.         {
  87.             for(int j = 1; j <= i; j++)
  88.                 for(int c = 0; c < 26; c++)
  89.                     if(G1.get(c) != G2.get(c))
  90.                     {
  91.                         ans[j] = c + 'a';
  92.                         G1.upd(); G2.upd();
  93.                         break;
  94.                     }
  95.             printf("%s\n", ans + 1);
  96.             return 0;
  97.         }
  99.     puts("Same");
  100.     return 0;
  101. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注