結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー IL_msta
提出日時 2015-11-01 06:52:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 6,501 bytes
コンパイル時間 2,469 ms
コンパイル使用メモリ 113,112 KB
実行使用メモリ 30,880 KB
最終ジャッジ日時 2024-09-13 06:49:21
合計ジャッジ時間 13,831 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 <valarray>
//#include <random>//xAOJ
/////////
#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;
/////////
/////////
inline long double dot(const valarray<long double>& A,const valarray<long double>& B ){
    return ( A * B ).sum();
}
inline long double norm(valarray<long double> &A ){
    return sqrt( (A * A).sum() );
}
//簡約ステップ
/*
入力 行列g g[i] = 基底 b_i
出力
    r 簡約したもの
    u μ(i,j) := <b_i,b_j*>/<b_j*,b_j*>  :(i>j)
    グラムシュミット係数
    この係数を簡約で1/2以下にしていく
    二等辺三角形、垂線底辺を２分する
*/
/*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]) / dot(r[j],r[j]);
        }
        r[i] = g[i];
        for(int j = 0; j < i; ++ j){
            r[i] = r[i] - u[i][j] * r[j];
        }
    }
}
*/
//グラムシュミット直交化ベクトルを計算
//Gram-Schmidt orthonormalization
//つまりcomputeGSO
void GSO(const vector< valarray<long double> > &B,
    vector< valarray<long double> >& Bstar,
    vector< valarray<long double> >& myu
    ){
    
    int N = B.size();
    //半分計算する
    for(int i=0;i<N;++i){
        for(int j=0;j<i;++j){
            myu[i][j] = dot( B[i],Bstar[j] ) / dot( Bstar[j],Bstar[j] );
            //
        }
        Bstar[i] = B[i];
        for(int j=0;j<i;++j){
            Bstar[i] -= myu[i][j] * Bstar[j];
        }
    }
}
vector< valarray<long double> > LLL(vector< valarray<long double> >& inB){
    //B B[i]が基底b_i
    //long double delta = 0.5;//
    int N = inB.size();//基底の数
    int M = 0;//基底の次元(要素数)
    if( N > 0){
        M = inB[0].size();
    }
    
    //グラムシュミット直交化 ベクトル Bstar[i]
    vector< valarray<long double> > B(N,valarray<long double>(M) );
    B = inB;
    vector< valarray<long double> > Bstar(N,valarray<long double>(M) );
    vector< valarray<long double> > myu(N,valarray<long double>(N) );
    //GSO(B,Bstar,myu);
    bool flag = true;
    for(;flag;){
        flag = false;
        GSO(B,Bstar,myu);
        int i=1;
        while( i < N ){
            for(int j=i-1; j>=0; --j){
                /*if(  dot( B[i]-B[j],B[i]-B[j] ) < dot( B[i],B[i] ) ){
                    B[i] = B[i]-B[j];
                    flag = true;
                }*/
                if( abs( myu[i][j] ) > 0.5 ){
                    long double keisuu = floor( myu[i][j] +0.5);//切り下げ関数
                    B[i] = B[i] - keisuu * B[j];
                    myu[i][j] -= keisuu;
                    
                    long long cZ = (long long)keisuu;
                    for(int k=0;k<N;++k){
                        inB[i][k] = (LL)inB[i][k] - cZ * (LL)inB[j][k];
                    }
                    GSO(B,Bstar,myu);
                }
            }
            /*
            |bi*|^2 >= (3/4 - μ(i,i-1)^2 )|b(i-1)|^2
            */
            
            if( dot( Bstar[i],Bstar[i])  <
                ((long double)3.0/4.0 - myu[i][i-1]*myu[i][i-1])*
                dot(Bstar[i-1],Bstar[i-1]) )
            
            /*if( dot(Bstar[i-1],Bstar[i-1]) >
                dot(Bstar[i],Bstar[i])*4 )
            */
            {
                swap( B[i-1], B[i] );
                swap( inB[i-1], inB[i] );
                GSO(B,Bstar,myu);
                i = max( i-1, 1);
            }else{
                ++i;
            }
        }
    }
    /*for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            cout << " " << B[i][j];
        }cout << endl;
    }*/
    return B;
}
LL inP,inB;
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) % inP;
        if( n & (1 << bit) ){
            ret = (ret + A) % inP;
        }
    }
    return ret;
}
void initbmp(){
    bmp[0][0] = 1;
    bmp[0][1] = inB % inP;
    for(int i=2;i<100001;++i){
        bmp[0][i] = ( bmp[0][i-1] * inB ) % inP;
    }
    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 ) % inP;
        }
    }
}
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] ) % inP;
    }
    return ret;
}
LL calH( vector<int> &v ){
    int len = v.size();
    LL ret = 0;
    for(int i=0;i<len;++i){
        ret = ( ret + bmp[ v[i] ][len-i-1] );
        if( ret >= inP ){
            ret = ret % inP;
        }
    }
    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(){
    /*vector< valarray<long double> > B(3,valarray<long double>(3));
    B[0][0] = 1;
    B[0][1] = 1;
    B[0][2] = 1;
    B[1][0] = -1;
    B[1][1] = 0;
    B[1][2] = 2;
    B[2][0] = 3;
    B[2][1] = 5;
    B[2][2] = 6;
    B = LLL(B);
    for(int i=0;i<3;++i){
        for(int j=0;j<3;++j){
            cout << " " << B[i][j];
        }cout << endl;
    }
    // 0 1 0
    // 1 0 1
    //-1 0 2
    return;*/
    cin >> inP >> inB;
    initbmp();
    const int Alpha = 26;
    int n;
    vector<int> ans;
    bool flag;
    n = 16;//
    for(;;){
        for(;;n+=4){
//          cout << n << endl;
            vector< valarray<long double> > B(n,valarray<long double>(n) );
            vector< valarray<long double> > getB(n,valarray<long double>(n) );
            for(int i=0;i<n;++i){
                for(int j=0;j<n;++j){
                    B[i][j] = 0;
                }
            }
            for(int i=0;i< n-1;++i){
                B[i][i+0] = (long double)(-inB);
                B[i][i+1] = 1;
            }
            B[n-1][0] = (long double)inP;
            //LLL
            //getB = LLL( B );
            B = LLL( B );
//          cout << B[0][0] << endl;
            for(int asd=0;asd<n;++asd){
                flag = true;
                for(int i=0;i<n;++i){
                    flag &= abs( B[asd][i] ) < Alpha;
                }
                if( flag ){
                    ans.resize( n );
                    for(int i=0;i<n;++i){
                        ans[i] = (int)B[asd][i];
                    }
                }else{
                    continue;
                }
                int len = n;
                while( len > 1 && ans[len-1] == 0 ){
                    --len;//reading 0
                }
                string S(len,'a');
                string T(len,'a');
                int temp;
                for(int i=0;i<len;++i){
                    temp = ans[len-1 -i];
                    if( temp >= 0 ){
                        //S[i]-T[i] = temp;
                        S[i] = 'a' + temp;
                        T[i] = 'a';
                    }else{
                        S[i] = 'a';
                        T[i] = 'a' - temp;
                    }
                }
                ULL SH,TH;
                SH = calH( S );
                TH = calH( T );
//              cout << SH << " " << TH << endl;
//              cout << S << endl;
//              cout << T << endl;
                if( SH == TH ){
                    cout << S << endl;
                    cout << T << endl;
                    return;
                }
            }
        }//for(n=16;;n+=4)      
    }
}
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