結果

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

ソースコード

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

#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
#include <sstream>
 
#include <algorithm>
#include <cmath>
 
#include <string>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <random>
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
/////////
using namespace::std;
/////////
/////////
ULL P,B;
vector< vector<ULL> > bmp(26,vector<ULL>(100001) );
ULL kake(ULL A, int n){
    //A*n
    ULL ret=0;
    for(int bit=31;bit>=0;--bit){
        ret = (ret + ret) % P;
        if( n & (1 << bit) ){
            ret = (ret + A) % P;
        }
    }
    return ret;
}
void initbmp(){
    bmp[0][0] = 1;
    bmp[0][1] = B % P;
    for(int i=2;i<100001;++i){
        bmp[0][i] = ( bmp[0][i-1] * B ) % P;
    }
    ULL add;
    for(int i=0;i<100001;++i){
        add = bmp[0][i];
        bmp[0][i] = kake( bmp[0][i], 97  );
        for(int j=1;j<26;++j){
            bmp[j][i] = ( bmp[j-1][i] + add ) % P;
        }
    }
}
ULL calH(string &str){
    int len = str.size();
    ULL ret = 0;
    for(int i=0;i<len;++i){
        ret = ( ret + bmp[str[i]-'a'][len-i-1] ) % P;
    }
    return ret;
}
ULL calH( vector<int> &v ){
    int len = v.size();
    ULL ret = 0;
    for(int i=0;i<len;++i){
        //if( 0 <= v[i] && v[i] < 26 )
        {
            //ret = ( ret + bmp[ v[i] ][len-i-1] ) % P;
            ret = ( ret + bmp[ v[i] ][len-i-1] );
            if( ret >= P ){
                ret = ret % P;
            }
        }
    }
    return ret;
}
void show( vector<int> &v ){
    char c;
    int len = v.size();
    for(int i=0;i<len;++i){
        c = v[i] + 'a';
        cout << c;
    }
    cout << '\n';
    return;
}
void solve(){
    
    cin >> P >> B;
    initbmp();
    ULL ah,bh;
    const int Lmax = 10000;
    vector<int> S(Lmax,0);
    vector<int> T(Lmax,0);
    random_device rnd;
    mt19937 mt(rnd());
    for(int i=0;i<Lmax;++i){
        S[i] = (mt()%26 + 26 )%26;
    }
    ah = calH( S );
    int i=0;
    show( S );
    for(;;){
        for(int i=0;i<Lmax;++i){
            //T[i] = (mt()%26 + 26 ) % 26;
            T[i] = mt()%26;
        }
        bh = calH( T );
        if( ah == bh ){
            break;
        }else{
            //cout << "x";
        }
    }
    show( T );
}
int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    cout << setprecision(16);//
    
    //cpp
    solve();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0