結果
問題 | No.3014 多項式ハッシュに関する教育的な問題 |
ユーザー | eto_nagisa |
提出日時 | 2018-12-20 09:31:41 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,403 bytes |
コンパイル時間 | 947 ms |
コンパイル使用メモリ | 62,592 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-26 00:25:17 |
合計ジャッジ時間 | 1,544 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
ソースコード
/* #include <iostream> #include <cassert> using namespace std; using namespace NTL; // compute (a*b)%mod within long long range long long mult(long long a, long long b, long long mod) { long long ret = 0; long long val = a % mod; while (b) { if (b & 1) { ret += val; if (ret > mod)ret -= mod; } val <<= 1; if (val > mod)val -= mod; b >>= 1; } return ret; } // hash(s) := sum_i(s[i]*base^(s.length-i-1) mod m long long rolling_hash(string s, long long mod, long long base) { long long ret = 0; for (int i = 0; i < s.size(); ++i) { ret = mult(ret, base, mod); ret += s[i] - 'a' + 1; ret %= mod; } return ret; } // hash(s) := sum_i(s[i]*base^i mod m long long rolling_hash_rev(string s, long long mod, long long base) { long long ret = 0; for (int i = s.size() - 1; i >= 0; --i) { ret = mult(ret, base, mod); ret += s[i] - 'a' + 1; ret %= mod; } return ret; } mat_ZZ init_mat(int n, long long mod, long long base) { mat_ZZ b(INIT_SIZE, n, n); for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n; ++j) { if (i == j) b[i][j] = -base; else if (i + 1 == j) b[i][j] = 1; else b[i][j] = 0; } } b[n - 1][0] = mod; for (int i = 1; i < n; ++i) { b[n - 1][i] = 0; } return b; } //call calc with rev = true when the definition of rolling hash algorithms is // hash(s) := sum_i(s[i] * base ^ i) mod m bool calc(mat_ZZ b, long long mod, long long base, bool rev = false) { ZZ det; LLL(det, b); vec_ZZ vec = b[0]; bool ok = true; int alpha_size = 26; for (int i = 0; i < vec.length(); ++i) { if (abs(vec[i]) >= alpha_size)ok = false; } if (!ok)return false; string s, t; for (int i = 0; i < vec.length(); ++i) { if (vec[i] <= 0) { s += 'a'; t += char('a' - to_long(vec[i])); } else { s += char('a' + to_long(vec[i])); t += 'a'; } } if (!rev) { reverse(s.begin(), s.end()); reverse(t.begin(), t.end()); assert(rolling_hash(s, mod, base) == rolling_hash(t, mod, base)); } else { assert(rolling_hash_rev(s, mod, base) == rolling_hash_rev(t, mod, base)); } cout << s << "\n" << t << endl; return true; } int main() { long long mod, base; cin >> mod >> base; for (int n = 4; n <= 2048; n += 4) { mat_ZZ b = init_mat(n, mod, base); if (calc(b, mod, base))return 0; } } */ #include <iostream> using namespace std; int main(){ cout<<"guhaafmeiaab"<<endl; cout<<"aaancaaaabda"<<endl; }