結果
| 問題 | No.3014 多項式ハッシュに関する教育的な問題 |
| ユーザー |
 Lay_ec
|
| 提出日時 | 2015-11-05 02:02:52 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,887 bytes |
| コンパイル時間 | 3,932 ms |
| コンパイル使用メモリ | 77,288 KB |
| 実行使用メモリ | 69,128 KB |
| 最終ジャッジ日時 | 2023-10-11 13:50:42 |
| 合計ジャッジ時間 | 16,507 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
ソースコード
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);
}
}