結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー Mi_Sawa
提出日時 2015-10-31 00:59:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,703 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 183,844 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-09-13 06:11:49
合計ジャッジ時間 2,594 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 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 = 10000;
    Int P, B; // cin >> P >> B;
    P = 1000000000000000003LL;
    B = 123456789987654321LL;
    vector<pair<Int, int>> powB(max_e+1);
    {
        powB[0].first = 1;
        rep(i, max_e) powB[i+1].first = mulMod(powB[i].first, B, P);
        rep(i, max_e+1) powB[i].second = max_e - i;
        sort(powB.begin(), powB.end());
        auto tmp = powB; powB.clear();
        rep(i, max_e) if(rnd(i+1) == 0) powB.emplace_back(tmp[i]);
        sort(powB.rbegin(), powB.rend());
    }
    unordered_map<Int, string> memo;
    while(true){
        string s(max_e, 'a');
        Int hash = 0;
        for(auto &pi : powB) if(rnd(2)){
            ++s[pi.second];
            hash = (hash + pi.first) % P;
        }
        for(auto &pi : powB){
            vector<pair<Int, int>> tmp;
            tmp.emplace_back(hash, 0);
            rep(i, 20) tmp.emplace_back((tmp.back().first + pi.first) % P, i+1);
            int e;
            tie(hash, e) = *max_element(all(tmp));
        }
        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