結果
問題 | No.8014 多項式ハッシュに関する教育的な問題 |
ユーザー | uwi |
提出日時 | 2018-09-28 16:47:02 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,766 bytes |
コンパイル時間 | 4,611 ms |
コンパイル使用メモリ | 83,880 KB |
実行使用メモリ | 74,976 KB |
最終ジャッジ日時 | 2024-10-12 04:53:48 |
合計ジャッジ時間 | 6,675 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ソースコード
package etc; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.BigInteger; import java.math.MathContext; import java.math.RoundingMode; import java.util.Arrays; import java.util.InputMismatchException; public class N3014 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { BigInteger[] res = hack(new BigInteger(ns()), new BigInteger(ns()), 25, 1); char[][] ret = restore(res, 'a'); for(char[] x : ret) { out.println(new String(x)); } } static MathContext mc = new MathContext(30); // static final BigInteger big = new BigInteger("999999999999999999999"); // static final BigInteger big = new BigInteger("999999"); static final BigInteger big = new BigInteger("9999999999"); /** * ハッシュ値が0となる列から、ハッシュ値が等しくなる2個の文字列を作成する * @param a * @param base 文字の最小値。'a'とか'A'とか。 * @return */ public static char[][] restore(BigInteger[] a, char base) { int n = a.length; char[][] ret = new char[2][n]; for(int i = 0;i < n;i++) { int v = a[i].intValue(); if(v < 0) { ret[1][i] = base; ret[0][i] = (char)(base - v); }else { ret[1][i] = (char)(base + v); ret[0][i] = base; } } return ret; } /** * 複数のmuls,modsを1個のmul,modにまとめる * @param muls * @param mods * @return */ public static BigInteger[] collect(long[] muls, long[] mods) { BigInteger cr = crtx(mods, muls); BigInteger mod = BigInteger.valueOf(1); for(long m : mods)mod = mod.multiply(BigInteger.valueOf(m)); return new BigInteger[] {cr, mod}; } public static BigInteger b(long x){ return BigInteger.valueOf(x); } public static BigInteger[] exGCD(BigInteger a, BigInteger b) { BigInteger p = BigInteger.ONE, q = BigInteger.ZERO, r = BigInteger.ZERO, s = BigInteger.ONE; while(b.signum() > 0){ BigInteger c = a.divide(b); BigInteger d; d = a; a = b; b = d.mod(b); d = p; p = q; q = d.subtract(c.multiply(q)); d = r; r = s; s = d.subtract(c.multiply(s)); } return new BigInteger[]{a, p, r}; } public static BigInteger crtx(long[] divs, long[] mods) { BigInteger div = b(divs[0]), mod = b(mods[0]); for(int i = 1;i < divs.length;i++){ BigInteger[] apr = exGCD(div, b(divs[i])); BigInteger mm = b(mods[i]).subtract(mod); if(mm.mod(apr[0]).signum() != 0)return b(-1); BigInteger da = div.divide(apr[0]); BigInteger ndiv = b(divs[i]).multiply(da); BigInteger nmod = apr[1].multiply(mm).multiply(da).add(mod).mod(ndiv); if(nmod.signum() < 0)nmod = nmod.add(ndiv); div = ndiv; mod = nmod; } return mod; } /** * (mul,mod)の多項式ハッシュに対し値が0となる列を見つける。 * @param mul * @param mod * @param w * @param least さがす最低長 * @return */ public static BigInteger[] hack(BigInteger mul, BigInteger mod, int w, int least) { BigInteger[] ret = null; BigInteger W = BigInteger.valueOf(w); for(int n = least;ret == null;n++) { BigInteger[][] B = new BigInteger[n][n+1]; BigInteger a = BigInteger.ONE; for(int i = n-1;i >= 0;i--) { Arrays.fill(B[i], BigInteger.ZERO); B[i][i] = BigInteger.ONE; B[i][n] = a.multiply(big); a = a.multiply(mul).mod(mod); } // for(int i = 0;i < n;i++) { // Arrays.fill(B[i], BigInteger.ZERO); // B[i][i] = BigInteger.ONE; // B[i][n] = a.multiply(big); // a = a.multiply(mul).mod(mod); // } BigInteger[][] res = reduce(B); inner: for(int i = 0;i < n;i++) { if(res[i][n].signum() == 0) { for(int j = 0;j < n;j++) { if(res[i][j].abs().compareTo(W) > 0)continue inner; } ret = Arrays.copyOf(res[i], n); break; } } } check(ret, mul, mod); return ret; } static void check(BigInteger[] v, BigInteger mul, BigInteger mod) { BigInteger h = BigInteger.ZERO; int n = v.length; for(int i = 0;i < n;i++) { h = h.multiply(mul).add(v[i]).mod(mod); } // for(int i = n-1;i >= 0;i--) { // h = h.multiply(mul).add(v[i]).mod(mod); // } assert h.signum() == 0; } /** * LLL * @param BO * @return */ public static BigInteger[][] reduce(BigInteger[][] BO) { int n = BO.length; int d = BO[0].length; // deepcopy BigInteger[][] B = new BigInteger[n][]; for(int i = 0;i < n;i++) { B[i] = Arrays.copyOf(BO[i], d); } BigDecimal[][] BA = new BigDecimal[n][]; BigDecimal delta = new BigDecimal("0.75"); // 0.25 < delta <= 1 recalculateOrthoginalization(0, BA, B); for(int k = 1;k < n;) { for(int j = k-1;j >= 0;j--) { BigDecimal mukj = mu(B[k], BA[j]); if(Math.abs(mukj.doubleValue()) > 0.5) { BigInteger rmu = mukj.setScale(0, RoundingMode.HALF_EVEN).toBigInteger(); for(int l = 0;l < d;l++) { B[k][l] = B[k][l].subtract(rmu.multiply(B[j][l])); } } } recalculateOrthoginalization(k, BA, B); BigDecimal mu = mu(B[k], BA[k-1]); // Lovasz condition if(norm(BA[k]).compareTo(delta.subtract(mu.multiply(mu, mc)).multiply(norm(BA[k-1]))) >= 0) { k++; }else { // swap BigInteger[] dum = B[k]; B[k] = B[k-1]; B[k-1] = dum; recalculateOrthoginalization(k-1, BA, B); k = Math.max(k-1, 1); } } return B; } /** * Gram-Schmidtの直交化のインデックスごと * @param ind * @param ovs * @param vs */ private static void recalculateOrthoginalization(int ind, BigDecimal[][] ovs, BigInteger[][] vs) { int D = vs[0].length; BigDecimal[] h = new BigDecimal[D]; for(int l = 0;l < D;l++)h[l] = new BigDecimal(vs[ind][l]); for(int l = 0;l < ind;l++){ BigDecimal dot = BigDecimal.ZERO; BigDecimal norm = BigDecimal.ZERO; for(int k = 0;k < D;k++){ dot = dot.add(ovs[l][k].multiply(new BigDecimal(vs[ind][k]), mc)); norm = norm.add(ovs[l][k].multiply(ovs[l][k], mc)); } if(norm.signum() == 0)continue; BigDecimal t = dot.divide(norm, mc); for(int k = 0;k < D;k++){ h[k] = h[k].subtract(ovs[l][k].multiply(t, mc)); } } ovs[ind] = h; } static BigDecimal mu(BigInteger[] b, BigDecimal[] ba) { return dot(b, ba).divide(norm(ba), mc); } public static BigDecimal norm(BigDecimal[] v) { BigDecimal n = BigDecimal.ZERO; for(BigDecimal w : v)n = n.add(w.multiply(w, mc)); return n; } public static BigDecimal dot(BigDecimal[] a, BigDecimal[] b) { BigDecimal ret = BigDecimal.ZERO; for(int i = 0;i < a.length;i++){ ret = ret.add(a[i].multiply(b[i], mc)); } return ret; } public static BigDecimal dot(BigInteger[] a, BigDecimal[] b) { BigDecimal ret = BigDecimal.ZERO; for(int i = 0;i < a.length;i++){ ret = ret.add(new BigDecimal(a[i]).multiply(b[i], mc)); } return ret; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new N3014().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }