結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー Mi_Sawa
提出日時 2015-10-31 01:56:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,929 bytes
コンパイル時間 1,596 ms
コンパイル使用メモリ 182,528 KB
実行使用メモリ 14,624 KB
最終ジャッジ日時 2024-09-13 06:12:56
合計ジャッジ時間 14,117 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define repsz(i,v) rep(i,(v).size())
using namespace std;
template<class C>int size(const C &c){ return c.size(); }
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}

using Int = long long;
Int mulMod(Int a, Int b, Int mod){//{{{
    if(a > b) swap(a, b);
    Int res = 0;
    for(; a;){
        if(a&1){
            res += b;
            if(res >= mod) res -= mod;
        }
        a >>= 1;
        b <<= 1;
        if(b >= mod) b -= mod;
    }
    return res;
}//}}}

unsigned int xor128(){
    //static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    static unsigned int x=129042, y=38923212, z=3829312, w=3893189;
    unsigned int t=x^(x<<11);
    x=y;y=z;z=w;
    return w=(w^(w>>19))^(t^(t>>8));
}
int rnd(int m){ return xor128() % m; }

bool solve(){
    constexpr int max_e = 100000;
    Int P, B; cin >> P >> B;
    // P = 1000000000000000003LL;
    // B = 123456789987654321LL;
    vector<pair<Int, int>> powB(max_e);
    {
        powB[0].first = 1;
        rep(i, max_e-1) powB[i+1].first = mulMod(powB[i].first, B, P);
        rep(i, max_e) powB[i].second = max_e - i - 1;
        sort(powB.begin(), powB.end());
    }
    unordered_map<Int, string> memo;
    string s(max_e, 'y');
    while(true){
        fill(all(s), 'y');
        Int hash = 0;
        for(auto &pi : powB) if(rnd(2)){
            ++s[pi.second];
            hash = hash + pi.first;
            if(hash >= P) hash -= P;
        }
        while(true){
            vector<tuple<Int, int, int>> tmp;
            for(int i = 1; i < 20; ++i){
                auto it = upper_bound(all(powB), make_pair(hash/i, 0));
                if(it == powB.begin()) continue;
                --it;
                tmp.emplace_back(hash - i * it->first, it->second, i);
            }
            if(tmp.empty()) break;
            Int h; int i, e; tie(h, i, e) = *min_element(all(tmp));
            if(s[i] - e < 'a') break;
            hash = h;
            s[i] -= e;
        }
        if(hash > 10000000000LL) continue;
        if(memo.count(hash)){
            if(memo[hash] == s) continue;
            cout << memo[hash] << endl << s << endl;
            return true;
        }
        // if((memo.size() & -memo.size()) == memo.size()){
        //     cout << memo.size() << endl;
        //     cout << hash << endl;
        // }
        memo[hash] = s;
    }

    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:
0