Submission #58560

---

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 long[] pow26 = 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) {
			map.put((int) (hash % B), String.valueOf(buf));
			return;
		}
		for (int i = 0; i < 26; ++i) {
			buf[pos] = (char) (i + 'a');
			memo(buf, pos + 1, (hash + table[pos + 1] * (i + 1)));
		}
	}

	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);
		}

		pow26[1] = 1;
		for (int i = 1; i < pow26.length - 1; ++i) {
			pow26[i + 1] = pow26[i] * 26;
		}

		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[i] = (char) (v + 'a');
			}
			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'));
					System.out.println(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;
	}

	static String suffix(long hash) {
		ArrayList<Integer> digit = new ArrayList<Integer>();
		ArrayList<Character> list = new ArrayList<Character>();
		while (hash > 0) {
			digit.add((int) (hash % 26));
			hash /= 26;
		}
		for (int i = 0; i < digit.size(); ++i) {
			if (digit.get(i) == 0) {
				int pos = i + 1;
				while (pos < digit.size() && digit.get(pos) == 0) {
					++pos;
				}
				if (pos == digit.size()) break;
				for (int j = i; j < pos; ++j) {
					digit.set(j, 26);
				}
				digit.set(pos, digit.get(pos) - 1);
			}
			list.add((char) (digit.get(i) - 1 + 'a'));
		}
		StringBuilder ret = new StringBuilder();
		for (int i = 0; i < list.size(); ++i) {
			ret.append(list.get(list.size() - 1 - i));
		}
		return ret.toString();
	}
}

Submission Info

Judge Result