Submission #58658

---

Source Code Expand

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int A, B;
	static long[] table = new long[50];
	static HashMap<Integer, String> map = new HashMap<Integer, String>();
	static int memoLen = 4;

	static void memo(char[] buf, int pos, long hash) {
		if (pos == memoLen) {
			//			System.out.println(hash + " " + (long)hash(String.valueOf(buf)) * A % B);
			map.put((int) hash, String.valueOf(buf));
			return;
		}
		for (int i = 0; i < 26; ++i) {
			buf[pos] = (char) (i + 'a');
			memo(buf, pos + 1, (hash + table[memoLen - pos] * (i + 1)) % B);
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		A = sc.nextInt();
		B = sc.nextInt();
		table[0] = 1;
		for (int i = 1; i < table.length; ++i) {
			table[i] = table[i - 1] * A % B;
		}
		{
			char[] buf = new char[memoLen];
			memo(buf, 0, 0);
		}

		HashSet<String> ans = new HashSet<String>();
		Random rand = new Random();
		char[] buf = new char[20];
		while (ans.size() < 100 && System.currentTimeMillis() - start < 1400) {
			long hash = 0;
			for (int i = 0; i < buf.length; ++i) {
				int v = rand.nextInt(26);
				hash += (v + 1) * table[i + memoLen + 1];
				hash %= B;
				buf[buf.length - 1 - i] = (char) (v + 'a');
			}
//			System.out.println(hash + " " + (long) hash(String.valueOf(buf)) * table[memoLen + 1] % B);
			for (int i = 1; i <= 26; ++i) {
				int key = (int) (B - hash - i);
				if (key < 0) key += B;
				if (map.containsKey(key)) {
					String suf = map.get(key);
					ans.add(String.valueOf(buf) + suf + (char) (i - 1 + 'a'));
					if (ans.size() == 100) break;
				}
			}
		}
		for (String s : ans) {
//			System.out.println(hash(s));
			System.out.println(s);
		}
	}

	static int hash(String s) {
		long h = 0;
		for (int i = 0; i < s.length(); ++i) {
			h = (h * A + (s.charAt(i) - 'a' + 1)) % B;
		}
		return (int) h;
	}

}

Submission Info

Judge Result