結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー anta
提出日時 2015-10-21 16:31:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 3,163 bytes
コンパイル時間 129 ms
コンパイル使用メモリ 21,120 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-07-22 11:22:10
合計ジャッジ時間 459 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//埋め込み解
#include <cstdio>
int main() {
    std::puts("urtynvwwtsgvkjpe");
    std::puts("jxvjzjihihyfamvh");
}
//以下、生成に使ったコード
//1GBのメモリだけを使い、4分以下で生成できた
#if 0
#include <cstdio>
#include <memory>
#include <cstring>
#include <cassert>
using namespace std;
struct Xor128 {
    unsigned x, y, z, w;
    Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
    unsigned operator()() {
        unsigned t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
    }
    unsigned operator()(unsigned n) { return operator()() % n; }
};
typedef unsigned long long ull;
inline ull modmult(ull x, ull y, ull MOD) {
    unsigned long long a = x, r = 0;
    while(y) {
        if(y & 1)
            if((r += a) >= MOD) r -= MOD;
        if((a += a) >= MOD) a -= MOD;
        y >>= 1;
    }
    return r;
}
inline void modadd(ull &x, ull y, ull MOD) {
    if((x += y) >= MOD) x -= MOD;
}
__forceinline void increamentHash(ull &curHash, char curString[], ull coeffZA[], ull powers[], int N, ull P, Xor128 &xor128) {
    int incPos;
    do {
        incPos = xor128() & 0xf;
    } while(incPos >= N);
    for(int i = incPos; i < N; ++ i) {
        if(curString[i] ++ == 'z') {
            curString[i] = 'a';
            modadd(curHash, coeffZA[i], P);
        } else {
            modadd(curHash, powers[i], P);
            break;
        }
    }
}
int main() {
    const ull P = 1000000000000000003ULL;
    const ull B = 123456789987654321ULL;
    const int TableBits = 28;
    const int N = 16;
    const int A = 26;
    assert(P < 1ULL << 63);
    assert(((P-1) >> TableBits) < (1ULL << 32));
    unique_ptr<unsigned[]> table(new unsigned[size_t(1) << TableBits]);
    memset(table.get(), 0, sizeof(unsigned) << TableBits);
    ull powers[N];
    powers[N - 1] = 1 % P;
    for(int i = N - 2; i >= 0; -- i)
        powers[i] = modmult(powers[i + 1], B, P);
    ull coeffZA[N];
    for(int i = 0; i < N; ++ i)
        coeffZA[i] = (P - modmult(powers[i], 'z' - 'a', P)) % P;
    char curString[N+1];
    ull initHash = 0;
    for(int i = 0; i < N; ++ i) {
        curString[i] = 'a';
        modadd(initHash, modmult(powers[i], 'a', P), P);
    }
    curString[N] = 0;
    ull curHash = initHash;
    Xor128 xor128;
    char secondString[N+1];
    ull targetHash;
    long long iter;
    size_t tableEntries = 0;
    for(iter = 0;; ++ iter) {
        if((iter & ((1U << 26) - 1)) == 0)
            fprintf(stderr, "iter = %lld, table = %lld\n",
            iter, (long long)tableEntries);
        unsigned tableIndex = curHash & ((1U << TableBits) - 1);
        unsigned tableValue = (unsigned)(curHash >> TableBits);
        unsigned t = table[tableIndex];
        if(t == 0) {
            table[tableIndex] = tableValue;
            ++ tableEntries;
        } else if(t == tableValue) {
            printf("iter = %lld: %s, %llu\n", iter, curString, curHash);
            memcpy(secondString, curString, sizeof(curString));
            targetHash = curHash;
            break;
        }
        increamentHash(curHash, curString, coeffZA, powers, N, P, xor128);
    }
    curHash = initHash;
    for(int i = 0; i < N; ++ i)
        curString[i] = 'a';
    xor128 = Xor128();
    for(iter = 0;; ++ iter) {
        if(curHash == targetHash)
            break;
        increamentHash(curHash, curString, coeffZA, powers, N, P, xor128);
    }
    printf("%s\n%s\n", curString, secondString);
    fprintf(stderr, "hash = %llu\n", curHash);
    return 0;
}
#endif
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0