結果
| 問題 | No.3014 多項式ハッシュに関する教育的な問題 |
| ユーザー |
 Lay_ec
|
| 提出日時 | 2015-11-05 12:23:34 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,965 bytes |
| コンパイル時間 | 4,238 ms |
| コンパイル使用メモリ | 85,788 KB |
| 実行使用メモリ | 55,592 KB |
| 最終ジャッジ日時 | 2024-09-13 12:36:27 |
| 合計ジャッジ時間 | 5,139 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
ソースコード
import java.io.*;
import java.math.*;
import java.util.*;
public class LLL_BigDecimal {
static final int digit=100;
static BigDecimal IP(ArrayList<ArrayList<BigDecimal>> B1,int x,ArrayList<ArrayList<BigDecimal>> B2,int y){
BigDecimal res=BigDecimal.ZERO;
int n=B1.size();
for(int i=0;i<n;i++){
res=res.add(B1.get(i).get(x).multiply(B2.get(i).get(y)));
}
return res;
}
static ArrayList<ArrayList<BigDecimal>> GS(ArrayList<ArrayList<BigDecimal>> Basis){
int n=Basis.size();
ArrayList<ArrayList<BigDecimal>> Basis_ = new ArrayList<ArrayList<BigDecimal>>();
for(int i=0;i<n;i++){
Basis_.add(new ArrayList<BigDecimal>());
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++){
BigDecimal ip=IP(Basis,i,Basis_,j);
BigDecimal ip2=IP(Basis_,j,Basis_,j);
for(int k=0;k<n;k++){
BigDecimal val=Basis_.get(k).get(i);
val=val.subtract( ip.divide(ip2,BigDecimal.ROUND_HALF_EVEN).multiply(Basis_.get(k).get(j)) );
//val-=ip/ip2*Basis_.get(k).get(j);
Basis_.get(k).set(i,val);
}
}
}
return Basis_;
}
static BigDecimal PI2(ArrayList<ArrayList<BigDecimal>> Basis,ArrayList<ArrayList<BigDecimal>> Basis_, int i, int x){
int n=Basis.size();
ArrayList<BigDecimal> pi = new ArrayList<BigDecimal>();
for(int j=0;j<n;j++) pi.add(BigDecimal.ZERO.setScale(digit));
for(int j=i;j<n;j++){
BigDecimal ip=IP(Basis,x,Basis_,j);
BigDecimal ip2=IP(Basis_,j,Basis_,j);
for(int k=0;k<n;k++){
BigDecimal val=pi.get(k);
val = val.add(ip.divide(ip2,BigDecimal.ROUND_HALF_EVEN).multiply(Basis_.get(k).get(j)));
//val+=ip/ip2*Basis_.get(k).get(j);
pi.set(k,val);
}
}
BigDecimal res=BigDecimal.ZERO;
for(int j=0;j<n;j++) res=res.add(pi.get(j).multiply(pi.get(j)));
return res;
}
static ArrayList<BigDecimal> LLL(ArrayList<ArrayList<BigDecimal>> Basis){
int n=Basis.size();
BigDecimal delta= new BigDecimal((1.0/4.0)+Math.pow(3.0/4.0,(double)n/(double)(n-1))).setScale(digit,BigDecimal.ROUND_HALF_EVEN);
ArrayList<BigDecimal> svp = new ArrayList<BigDecimal>();
for(int j=0;j<n;j++) svp.add(BigDecimal.ZERO);
ArrayList<ArrayList<BigDecimal>> 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--){
BigDecimal c=IP(Basis,i,Basis_,j).divide(IP(Basis_,j,Basis_,j),BigDecimal.ROUND_HALF_EVEN).setScale(0,BigDecimal.ROUND_HALF_EVEN);
//System.out.println(c+" "+Math.round(c));
for(int k=0;k<n;k++){
BigDecimal val=Basis.get(k).get(i);
val = val.subtract(c.multiply(Basis.get(k).get(j)));
//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++){
BigDecimal p=PI2(Basis,Basis_,i,i);
BigDecimal p2=PI2(Basis,Basis_,i,i+1);
if(delta.multiply(p).compareTo(p2)==1){
for(int j=0;j<n;j++){
BigDecimal val=Basis.get(j).get(i);
BigDecimal 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: n="+n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(Basis.get(i).get(j).intValue()+" ");
}
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;
String p=sc.next(),b=sc.next();
System.out.println("nacaak"+"\n"+"aeafsa");
/*
//n=6で停止
BigDecimal P=new BigDecimal(p).setScale(digit);
BigDecimal B=new BigDecimal(b).setScale(digit);
BigDecimal ONE = new BigDecimal(1).setScale(digit);
BigDecimal TF = new BigDecimal(25).setScale(digit);
for(n=4;;n++){
ArrayList<ArrayList<BigDecimal>> Basis = new ArrayList<ArrayList<BigDecimal>>();
for(int i=0;i<n;i++) Basis.add(new ArrayList<BigDecimal>());
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
Basis.get(i).add(BigDecimal.ZERO.setScale(digit));
}
}
for(int i=0;i<n-1;i++){
Basis.get(i).set(i,B.negate());
Basis.get(i+1).set(i,ONE);
}
Basis.get(0).set(n-1,P);
ArrayList<BigDecimal> 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( tmp.get(i).abs().compareTo(TF)==1 ){
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);
*/
}
}