結果

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

ソースコード

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

#include <vector>
#include <valarray>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
typedef long double R;
typedef valarray<R> VecR;
typedef vector<VecR> MatR;
inline R dot(const VecR &x, const VecR &y) {
    return (x * y).sum();
}
inline R norm(const VecR &x) {
    return dot(x, x);
}
void computeGSO(const MatR &g, MatR &r, MatR &u) {
    int n = g.size();
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j < i; ++ j)
            u[i][j] = dot(g[i], r[j]) / norm(r[j]);
        r[i] = g[i];
        for(int j = 0; j < i; ++ j)
            r[i] -= u[i][j] * r[j];
    }
}
void basisReduction(vector<vector<long long> > &f) {
    int n = f.size();
    MatR g(n), r(n), u(n);
    for(int i = 0; i < n; ++ i) {
        assert(f[i].size() == n);
        g[i].resize(n);
        for(int j = 0; j < n; ++ j)
            g[i][j] = (R)f[i][j];
        r[i].resize(n);
        u[i].resize(i);
    }
    computeGSO(g, r, u);
    for(int i = 1; i < n; ) {
        for(int j = i-1; j >= 0; -- j) {
            if(abs(u[i][j]) < .5) continue;
            R c = floor(u[i][j] + .5);
            g[i] -= c * g[j];
            long long cZ = (long long)c;
            for(int k = 0; k < n; ++ k)
                f[i][k] -= cZ * f[j][k];
            computeGSO(g, r, u);
        }
        if(i > 0 && norm(r[i-1]) > norm(r[i]) * 2) {
            swap(g[i-1], g[i]);
            swap(f[i-1], f[i]);
            computeGSO(g, r, u);
            -- i;
        }else {
            ++ i;
        }
    }
}
long long calcHash(const string &S, long long P, long long B) {
    long long h = 0;
    for(int i = 0; i < (int)S.size(); ++ i)
        h = ((__int128)h * B + S[i]) % P;
    return h;
}
int main() {
    assert(sizeof(long double) >= 10);
    const int Alphas = 26;
    long long P, B;
    while(cin >> P >> B) {
        int n;
        vector<int> poly;
        for(n = 16;; n += 4) {
            vector<vector<long long> > L(n, vector<long long>(n, 0));
            for(int i = 0; i < n - 1; ++ i) {
                L[i][i + 0] = -B;
                L[i][i + 1] = 1;
            }
            L[n - 1][0] = P;
            basisReduction(L);
            bool ok = true;
            for(int i = 0; i < n; ++ i)
                ok &= abs(L[0][i]) < Alphas;
            if(ok) {
                poly.resize(n);
                for(int i = 0; i < n; ++ i)
                    poly[i] = (int)L[0][i];
                break;
            }
        }
        int len = n;
        while(len > 1 && poly[len - 1] == 0) -- len;
        string S(len, '?'), T(len, '?');
        for(int i = 0; i < len; ++ i) {
            int a = poly[len - 1 - i];
            if(a >= 0) {
                S[i] = 'a' + a;
                T[i] = 'a';
            } else {
                S[i] = 'a';
                T[i] = 'a' - a;
            }
        }
        assert(calcHash(S, P, B) == calcHash(T, P, B));
        cout << S << endl;
        cout << T << endl;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0