結果
| 問題 | No.599 回文かい |
| ユーザー |
 tanzaku
|
| 提出日時 | 2017-11-24 22:53:37 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,350 bytes |
| コンパイル時間 | 2,291 ms |
| コンパイル使用メモリ | 87,820 KB |
| 実行使用メモリ | 54,752 KB |
| 最終ジャッジ日時 | 2024-11-27 07:44:10 |
| 合計ジャッジ時間 | 8,404 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 56 ms
50,468 KB |
| testcase_01 | AC | 56 ms
50,364 KB |
| testcase_02 | AC | 55 ms
50,132 KB |
| testcase_03 | AC | 54 ms
50,344 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| evil_0.txt | WA | - |
ソースコード
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.Reader;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyInput in = new MyInput(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskC solver = new TaskC();
solver.solve(1, in, out);
out.close();
}
static class TaskC {
static final int mod = (int) 1e9 + 7;
char[] cs;
long[] memo;
RollingHashMod hash;
public void solve(int testNumber, MyInput in, PrintWriter out) {
cs = in.nextChars();
hash = new RollingHashMod(cs);
memo = new long[cs.length + 1];
out.println(rec(0));
}
long rec(int len) {
if (memo[len] == 0) {
long ans = 1;
for (int i = 1; (i + len) * 2 < cs.length; i++) {
// dump(i, len, cs.length);
if (hash.hash(len, i + len) == hash.hash(cs.length - len - i, cs.length - len)) {
ans += rec(len + i);
}
}
memo[len] = ans % mod;
}
return memo[len];
}
}
static class MyInput {
private final BufferedReader in;
private static int pos;
private static int readLen;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500 * 8 * 2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static {
for (int i = 0; i < 10; i++) {
isDigit['0' + i] = true;
}
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}
public MyInput(InputStream is) {
in = new BufferedReader(new InputStreamReader(is));
}
public int read() {
if (pos >= readLen) {
pos = 0;
try {
readLen = in.read(buffer);
} catch (IOException e) {
throw new RuntimeException();
}
if (readLen <= 0) {
throw new MyInput.EndOfFileRuntimeException();
}
}
return buffer[pos++];
}
public char nextChar() {
while (true) {
final int c = read();
if (!isSpace[c]) {
return (char) c;
}
}
}
int reads(int len, boolean[] accept) {
try {
while (true) {
final int c = read();
if (accept[c]) {
break;
}
if (str.length == len) {
char[] rep = new char[str.length * 3 / 2];
System.arraycopy(str, 0, rep, 0, str.length);
str = rep;
}
str[len++] = (char) c;
}
} catch (MyInput.EndOfFileRuntimeException e) {
}
return len;
}
public char[] nextChars() {
int len = 0;
str[len++] = nextChar();
len = reads(len, isSpace);
return Arrays.copyOf(str, len);
}
static class EndOfFileRuntimeException extends RuntimeException {
}
}
static class RollingHashMod {
private static final int[] LARGE_PRIMES = new int[]{
1000000007, 1000000009, 1000000021, 1000000033,
1000000087, 1000000093, 1000000097, 1000000103,
1000000123, 1000000181, 1000000207, 1000000223,
1000000241, 1000000271, 1000000289, 1000000297,
1000000321, 1000000349, 1000000363, 1000000403,
};
private static final int HASH_NUM = 2;
private static final long RADIX = 1000000003;
private int n;
private static int[] primes;
private int[][] pow;
private int[][] table;
private int[][] table2;
public RollingHashMod(char[] str) {
if (primes == null) {
// final Random random = new Random(System.currentTimeMillis());
final Random random = new Random(0);
primes = new int[HASH_NUM];
for (int i = 0; i < HASH_NUM; i++) {
final int idx = random.nextInt(LARGE_PRIMES.length - i);
primes[i] = LARGE_PRIMES[idx];
LARGE_PRIMES[idx] = LARGE_PRIMES[LARGE_PRIMES.length - i - 1];
LARGE_PRIMES[LARGE_PRIMES.length - i - 1] = primes[i];
}
}
n = str.length;
table = new int[HASH_NUM][n + 1];
table2 = new int[HASH_NUM][n + 1];
pow = new int[HASH_NUM][n + 1];
for (int j = 0; j < HASH_NUM; j++) {
final int p = primes[j];
pow[j][0] = 1;
for (int i = 0; i < n; i++) {
table[j][i + 1] = (int) (((long) table[j][i] * RADIX + str[i]) % p);
table2[j][i + 1] = (int) (((long) table2[j][i] * RADIX + str[n - 1 - i]) % p);
pow[j][i + 1] = (int) ((long) pow[j][i] * RADIX % p);
}
}
}
public long hash(int i, int j) {
assert (i <= j);
long h0 = table[0][j] - (long) table[0][i] * pow[0][j - i] % primes[0];
long h1 = table[1][j] - (long) table[1][i] * pow[1][j - i] % primes[1];
if (h0 < 0) h0 += primes[0];
if (h1 < 0) h1 += primes[1];
return h0 << 32 | h1;
}
}
}