結果
| 問題 | No.8014 多項式ハッシュに関する教育的な問題 |
| ユーザー |
 uwi
|
| 提出日時 | 2018-09-28 16:48:44 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 1,153 ms / 5,000 ms |
| コード長 | 9,814 bytes |
| コンパイル時間 | 4,437 ms |
| コンパイル使用メモリ | 97,972 KB |
| 実行使用メモリ | 68,716 KB |
| 最終ジャッジ日時 | 2024-10-12 04:53:58 |
| 合計ジャッジ時間 | 7,252 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
ソースコード
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 mod = new BigInteger(ns());
BigInteger mul = new BigInteger(ns());
BigInteger[] res = hack(mul, mod, 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)); }
}