結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー Lay_ec
提出日時 2015-11-05 02:02:52
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 5,887 bytes
コンパイル時間 5,346 ms
コンパイル使用メモリ 81,004 KB
実行使用メモリ 66,824 KB
最終ジャッジ日時 2024-09-13 12:33:21
合計ジャッジ時間 16,461 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.*;
import java.math.*;
import java.util.*;
public class LLL {
    static double IP(ArrayList<ArrayList<Double>> B1,int x,ArrayList<ArrayList<Double>> B2,int y){
        double res=0;
        int n=B1.size();
        for(int i=0;i<n;i++){
            res+=B1.get(i).get(x)*B2.get(i).get(y);
        }
        
        return res;
        
        
    }
    
    static ArrayList<ArrayList<Double>> GS(ArrayList<ArrayList<Double>> Basis){
        int n=Basis.size();
        ArrayList<ArrayList<Double>> Basis_ = new ArrayList<ArrayList<Double>>();
        for(int i=0;i<n;i++){
            Basis_.add(new ArrayList<Double>());
            for(int j=0;j<n;j++){
                Basis_.get(i).add(Basis.get(i).get(j));
            }
        }
        
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                double ip=IP(Basis,i,Basis_,j);
                double ip2=IP(Basis_,j,Basis_,j);
                for(int k=0;k<n;k++){
                    double val=Basis_.get(k).get(i);
                    val-=ip/ip2*Basis_.get(k).get(j);
                    Basis_.get(k).set(i,val);
                }
            }
        }
        
        return Basis_;
    }
    
    static double PI2(ArrayList<ArrayList<Double>> Basis,ArrayList<ArrayList<Double>> Basis_, int i, int x){
        int n=Basis.size();
        ArrayList<Double> pi = new ArrayList<Double>();
        for(int j=0;j<n;j++) pi.add(0.0);
        
        for(int j=i;j<n;j++){
            double ip=IP(Basis,x,Basis_,j);
            double ip2=IP(Basis_,j,Basis_,j);
            
            for(int k=0;k<n;k++){
                double val=pi.get(k);
                val+=ip/ip2*Basis_.get(k).get(j);
                pi.set(k,val);
            }
        }
        
        double res=0;
        for(int j=0;j<n;j++) res+=pi.get(j)*pi.get(j);
        return res;
        
    }
    
    static ArrayList<Double> LLL(ArrayList<ArrayList<Double>> Basis){
        int n=Basis.size();
        double delta=(1.0/4.0)+Math.pow(3.0/4.0,(double)n/(double)(n-1));
        ArrayList<Double> svp = new ArrayList<Double>();
        for(int j=0;j<n;j++) svp.add(0.0);
        ArrayList<ArrayList<Double>> Basis_=GS(Basis);
        while(true){
/*
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    System.out.print(Basis.get(i).get(j)+" ");
                }
                System.out.println();
            }
            System.out.println();
*/
            for(int i=0;i<n;i++){
                for(int j=i-1;j>=0;j--){
                    double c=(IP(Basis,i,Basis_,j)/IP(Basis_,j,Basis_,j));
                    //System.out.println(c+" "+Math.round(c));
                    for(int k=0;k<n;k++){
                        double val=Basis.get(k).get(i);
                        val-=Math.round(c)*Basis.get(k).get(j);
                        Basis.get(k).set(i,val);
                        Basis_=GS(Basis);
                    }
                }
            }
            
            boolean cont=false;
            for(int i=0;i<n-1;i++){
                double p=PI2(Basis,Basis_,i,i);
                double p2=PI2(Basis,Basis_,i,i+1);
                if(delta*p>p2){
                    for(int j=0;j<n;j++){
                        double val=Basis.get(j).get(i);
                        double val2=Basis.get(j).get(i+1);
                        Basis.get(j).set(i,val2);
                        Basis.get(j).set(i+1,val);
                    }
                    Basis_=GS(Basis);
                    cont=true;
                }
                if(cont) break;
            }
            
            if(cont) continue;
            else{
/*
                System.out.println("result");
                for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++){
                        System.out.print(Basis.get(i).get(j)+" ");
                    }
                    System.out.println();
                }
*/
                for(int i=0;i<n;i++){
                    svp.set(i,Basis.get(i).get(0));
                }
                return svp;
            }
        }
    }
    
    
    public static void main(String args[]) throws IOException{ 
        Scanner sc = new Scanner(System.in);
        int n;
        ArrayList<Integer> coe;
        double p=sc.nextDouble(),b=sc.nextDouble();
        for(n=4;;n+=4){
            ArrayList<ArrayList<Double>> Basis = new ArrayList<ArrayList<Double>>();
            for(int i=0;i<n;i++) Basis.add(new ArrayList<Double>());
            
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    Basis.get(i).add(0.0);
                }
            }
            
            for(int i=0;i<n-1;i++){
                Basis.get(i).set(i,-b);
                Basis.get(i+1).set(i,1.0);
            }
            Basis.get(0).set(n-1,p);
            
            ArrayList<Double> tmp=LLL(Basis);
            Collections.reverse(tmp);
            
            coe=new ArrayList<Integer>();
            for(int i=0;i<n;i++){
                coe.add(tmp.get(i).intValue());
            }
            
            boolean ok=true;
            for(int i=0;i<n;i++){
                if(Math.abs(coe.get(i))>25){
                    ok=false;
                }
            }
            
            if(ok){
                break;
            }
        }
        
        char[] s = new char[n];
        char[] t = new char[n];
        
        for(int i=0;i<n;i++){
            int smt=coe.get(i).intValue();
            if(smt>=0){
                s[i]=(char)('a'+smt);
                t[i]='a';
            }else{
                s[i]='a';
                t[i]=(char)('a'-smt);
            }
        }
        
        String S = new String(s);
        String T = new String(t);
        System.out.println(S);
        System.out.println(T);
        
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0