結果
| 問題 | No.3105 Міжнародний підрядок саміт |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2023-04-16 18:49:13 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 764 ms / 3,153 ms |
| コード長 | 15,224 bytes |
| コンパイル時間 | 4,593 ms |
| コンパイル使用メモリ | 90,856 KB |
| 実行使用メモリ | 75,492 KB |
| 最終ジャッジ日時 | 2024-10-12 02:12:53 |
| 合計ジャッジ時間 | 7,939 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 281 ms
74,976 KB |
| testcase_01 | AC | 764 ms
75,056 KB |
| testcase_02 | AC | 360 ms
74,864 KB |
| testcase_03 | AC | 720 ms
75,492 KB |
| testcase_04 | AC | 379 ms
75,392 KB |
ソースコード
package yukicoder_9352;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.NoSuchElementException;
public class Main3 {
public static void main(String[] args) {
new Main3();
}
public Main3() {
InputChecker ic = new InputChecker(System.in);
java.io.PrintWriter out = new java.io.PrintWriter(System.out);
solve(ic, out);
out.flush();
}
public void solve(InputChecker ic, java.io.PrintWriter out) {
int T = ic.nextInt(1, 6000);
if (!isPrime(T)) throw new AssertionError(T + "is not prime");
ic.readNewLine();
int sum = 0;
HashMap<Integer, Data> data = new HashMap<>();
for (int i : new int[] { 2, 3, 5, 7, 11, 13 }) {
data.put(i, new Data(i));
}
while (T-- > 0) {
int N = ic.nextInt(1, 300);
if (!isPrime(N)) throw new AssertionError(N + " is not prime");
ic.nextChar(' ');
int P = ic.nextInt(100_000_000, 1_000_000_000);
if (!isPrime(P)) throw new AssertionError(P + " is not prime");
ic.readNewLine();
sum += N;
int[] A = new int[N];
for (int i = 0; i < N; ++i) {
A[i] = ic.nextInt(1, 1_000_000_000);
if (!isPrime(A[i])) throw new AssertionError(A[i] + " is not prime");
if (i == N - 1) ic.readNewLine();
else ic.nextChar(' ');
}
for (int i = 2; i < N; ++i) if (A[i] - A[i - 1] != A[1] - A[0])
throw new AssertionError(Arrays.toString(A) + " is not arithmetic progression"); // 等差数列
int a = A[0], d = A[1] - A[0];
if (d == 0) {
long ans = (long)pow(2, N - 1, P) * a;
System.out.println(ans % P);
} else {
long ans = data.get(N).calc(a, d);
System.out.println(ans % P);
}
}
if (sum > 6000) throw new AssertionError("sum N is over 6000: " + sum);
ic.checkEOF();
}
static final class Data {
int N;
static final class Search {
final long shift, aWeight;
final int first;
final int[] left, right;
Search(BitSet set, int positive, int N, int M) {
shift = N * (N + 1) / 2;
aWeight = 2 * positive - M;
first = set.nextSetBit(0);
int last = set.previousSetBit(set.length());
left = new int[last - first + 1];
right = new int[left.length];
left[0] = first;
for (int i = 1; i < left.length; ++i) {
if (set.get(i + first)) left[i] = i + first;
else left[i] = left[i - 1];
}
right[right.length - 1] = last;
for (int i = left.length - 1; i >= 0; --i) {
if (set.get(i + first)) right[i] = i + first;
else right[i] = right[i + 1];
}
}
long calc(int a, int d) { // 初項a, 公差dの数列
long weight = a * aWeight;
long mid = shift - weight / d;
if (first >= mid) return Math.abs(weight + (first - shift) * d); // 最適: a - first d
int last = first + left.length - 1;
if (mid >= last) return Math.abs(weight + (last - shift) * d); // 最適: a - last d
int check = (int) mid - first;
int l = left[check], r = right[check];
return Math.min(Math.abs(weight + (l - shift) * d), Math.abs(weight + (r - shift) * d)); // 最適は隣接するどちらか
}
}
Search[][] compress; // compress[S][x]: {0,1,…,N-1}の部分集合Sに対して、x個を正として選ぶ時に作れる答え
Data(int N) {
this.N = N;
compress = new Search[1 << N][];
BitSet[][] dp = dp(N);
for (int i = 1; i < compress.length; ++i) {
int len = Integer.bitCount(i);
Search[] array = compress[i] = new Search[len + 2 >> 1];
for (int j = 0; j < array.length; ++j) array[j] = new Search(dp[i][j], j, N, len);
}
}
private BitSet[][] dp(int N) {
BitSet[][] dp = new BitSet[1 << N][N + 1]; // dp[S][x]: {0,1,…,N-1}の部分集合Sに対して、x個を正として選ぶ時に作れる総和
int mid = N * (N + 1) / 2, setLen = mid << 1 | 1;
for (int i = 0; i < dp.length; ++i) {
int len = Integer.bitCount(i);
{ // 初項
dp[i][len] = new BitSet(setLen); // 全部を正で選ぶ
int sum = mid;
for (int j = 0; j < N; ++j) if ((i >> j & 1) != 0) sum += j;
dp[i][len].set(sum);
}
for (int j = 0; j < len; ++j) {
dp[i][j] = new BitSet(setLen);
for (int k = 0; k < N; ++k) {
if ((i >> k & 1) == 0) continue;
dp[i][j].or(dp[i ^ 1 << k][j].get(k, setLen));
}
}
}
return dp;
}
long calc(int a, int d) {
long sum = 0;
for (int i = 1; i < compress.length; ++i) {
long min = Long.MAX_VALUE;
for (Search s : compress[i]) {
long calc = s.calc(a, d);
min = Math.min(min, calc);
}
sum += min;
}
return sum;
}
}
public static class Barrett {
private final int mod;
private final long h, l;
private final long MAX = 1L << 62;
private final int MASK = (1 << 31) - 1;
Barrett(final int mod) {
this.mod = mod;
final long t = MAX / mod;
h = t >>> 31;
l = t & MASK;
}
int reduce(final long x) {
final long xh = x >>> 31, xl = x & MASK;
long z = xl * l;
z = xl * h + xh * l + (z >>> 31);
z = xh * h + (z >>> 31);
int ret = (int) (x - z * mod);
return ret < 0 || ret >= mod ? ret - mod : ret;
}
}
private static boolean isSPRP(Barrett n, int a) {
int d = n.mod - 1, s = Integer.numberOfTrailingZeros(d);
d >>= s;
int cur = 1, pw = d;
do {
if ((pw & 1) != 0) cur = n.reduce((long) cur * a);
a = n.reduce((long) a * a);
pw >>= 1;
} while (pw != 0);
if (cur == 1) return true;
while (s-- > 0) {
if (cur == n.mod - 1) return true;
cur = n.reduce((long) cur * cur);
}
return false;
}
private static final int bases[] = { 15591, 2018, 166, 7429, 8064, 16045, 10503, 4399, 1949, 1295, 2776, 3620, 560,
3128, 5212, 2657, 2300, 2021, 4652, 1471, 9336, 4018, 2398, 20462, 10277, 8028, 2213, 6219, 620, 3763, 4852,
5012, 3185, 1333, 6227, 5298, 1074, 2391, 5113, 7061, 803, 1269, 3875, 422, 751, 580, 4729, 10239, 746,
2951, 556, 2206, 3778, 481, 1522, 3476, 481, 2487, 3266, 5633, 488, 3373, 6441, 3344, 17, 15105, 1490, 4154,
2036, 1882, 1813, 467, 3307, 14042, 6371, 658, 1005, 903, 737, 1887, 7447, 1888, 2848, 1784, 7559, 3400,
951, 13969, 4304, 177, 41, 19875, 3110, 13221, 8726, 571, 7043, 6943, 1199, 352, 6435, 165, 1169, 3315, 978,
233, 3003, 2562, 2994, 10587, 10030, 2377, 1902, 5354, 4447, 1555, 263, 27027, 2283, 305, 669, 1912, 601,
6186, 429, 1930, 14873, 1784, 1661, 524, 3577, 236, 2360, 6146, 2850, 55637, 1753, 4178, 8466, 222, 2579,
2743, 2031, 2226, 2276, 374, 2132, 813, 23788, 1610, 4422, 5159, 1725, 3597, 3366, 14336, 579, 165, 1375,
10018, 12616, 9816, 1371, 536, 1867, 10864, 857, 2206, 5788, 434, 8085, 17618, 727, 3639, 1595, 4944, 2129,
2029, 8195, 8344, 6232, 9183, 8126, 1870, 3296, 7455, 8947, 25017, 541, 19115, 368, 566, 5674, 411, 522,
1027, 8215, 2050, 6544, 10049, 614, 774, 2333, 3007, 35201, 4706, 1152, 1785, 1028, 1540, 3743, 493, 4474,
2521, 26845, 8354, 864, 18915, 5465, 2447, 42, 4511, 1660, 166, 1249, 6259, 2553, 304, 272, 7286, 73, 6554,
899, 2816, 5197, 13330, 7054, 2818, 3199, 811, 922, 350, 7514, 4452, 3449, 2663, 4708, 418, 1621, 1171,
3471, 88, 11345, 412, 1559, 194 };
public static boolean isPrime(final int x) {
if (x == 2 || x == 3 || x == 5 || x == 7) return true;
if ((x & 1) == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false;
if (x < 121) return x > 1;
return checkPrime(x);
}
private static boolean checkPrime(final int x) {
if (x < 121) return x > 1;
long h = x;
h = (h >> 16 ^ h) * 0x45d9f3b;
h = (h >> 16 ^ h) * 0x45d9f3b;
h = (h >> 16 ^ h) & 0xFF;
return isSPRP(new Barrett(x), bases[(int) h]);
}
public static int exponent10(int n, int e) {
return n * pow(10, e);
}
public static long exponent10L(int n, int e) {
return n * pow(10L, e);
}
public static int pow(int a, int b) {
int ans = 1;
for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static int pow(int a, long b, int P) {
long ans = 1;
for (long mul = a; b > 0; b >>= 1, mul = mul * mul % P) if ((b & 1) != 0) ans = ans * mul % P;
return (int)ans;
}
public static long pow(long a, long b) {
long ans = 1;
for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static class CharSet {
private final BitSet set = new BitSet(256);
public void add(char... c) {
for (char i : c) set.set(i);
}
public void add(CharSet... s) {
for (CharSet i : s) set.or(i.set);
}
public boolean contains(char... c) {
for (char i : c) if (!set.get(i)) return false;
return true;
}
public boolean contains(String s) {
return contains(s.toCharArray());
}
private static final class Chars extends CharSet {
public Chars(char... c) {
super.add(c);
}
public Chars(CharSet... s) {
super.add(s);
}
@Override
public void add(char... c) {
throw new UnsupportedOperationException();
}
@Override
public void add(CharSet... s) {
throw new UnsupportedOperationException();
}
}
public static final CharSet NUMBER = new Chars('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
public static final CharSet LOWER = new Chars('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');
public static final CharSet UPPER = new Chars('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z');
public static final CharSet ALPHABET = new Chars(LOWER, UPPER);
}
public static class InputChecker {
private InputStream in;
private final byte[] buffer = new byte[1024];
private final byte[] undo = new byte[1024];
private int undoSize = 0;
private int read = 0;
private int length = 0;
public InputChecker(InputStream in) {
this.in = in;
}
public final void setInputStream(InputStream in) { this.in = in; }
public final void setInputStream(File in) {
try {
this.in = new FileInputStream(in);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
private boolean hasNextByte() {
if (undoSize > 0) return true;
if (read < length) return true;
read = 0;
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return length > 0;
}
private byte readByte() {
if (hasNextByte()) return undoSize > 0 ? undo[--undoSize] : buffer[read++];
throw new NoSuchElementException();
}
private void undo(byte b) {
undo[undoSize++] = b;
}
private void undo(char c) {
if ((c & 0xFF80) == 0) {
undo((byte) c);
return;
}
undo((byte) (c & 0x3F | 0x80));
if ((c & 0xF800) == 0) {
undo((byte) (c >> 6 & 0x1F | 0xC0));
} else {
undo((byte) (c >> 6 & 0x3F | 0x80));
undo((byte) (c >> 12 | 0xE0));
}
}
public final boolean hasNext() {
return hasNextByte();
}
public final char nextChar() {
byte b = readByte();
if ((b & 0x80) == 0) return (char) b;
if ((b & 0x20) == 0) return (char) ((b & 0x1F) << 6 | readByte() & 0x3F);
return (char) ((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | readByte() & 0x3F);
}
public final char nextChar(char estimate) {
char c = nextChar();
if (estimate == c) return estimate;
undo(c);
throw new AssertionError();
}
public final char nextChar(CharSet estimate) {
char c = nextChar();
if (estimate.contains(c)) return c;
undo(c);
throw new AssertionError();
}
public final void readNewLine() {
char c = nextChar();
if (c == '\r') {
c = nextChar();
if (c != '\n') undo(c);
return;
} else if (c == '\n') return;
undo(c);
throw new AssertionError();
}
public final void checkEOF() {
if (hasNextByte()) throw new AssertionError();
}
public final String next(CharSet contains) {
StringBuilder sb = new StringBuilder();
try {
do {
char c = nextChar();
if (!contains.contains(c)) {
undo(c);
return sb.toString();
}
sb.append(c);
} while (true);
} catch (NoSuchElementException e) {
if (sb.length() <= 0) throw new AssertionError();
return sb.toString();
}
}
public final int nextInt() {
byte b = readByte();
int n = 0;
if (b == '-') {
if (!isNumber(b = readByte())) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while (isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {}
return n;
}
if (!isNumber(b)) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while (isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {}
return n;
}
public final int nextInt(int min, int max) {
int n = nextInt();
if (min <= n && n <= max) return n;
throw new NumberFormatException();
}
private static boolean isNumber(byte c) {
return '0' <= c && c <= '9';
}
public final long nextLong() {
byte b = readByte();
long n = 0;
if (b == '-') {
if (!isNumber(b = readByte())) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while (isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {}
return n;
}
if (!isNumber(b)) {
undo(b);
throw new NumberFormatException();
}
try {
if (b == '0') {
if (!isNumber(b = readByte())) {
undo(b);
return 0;
}
throw new NumberFormatException();
}
do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while (isNumber(b = readByte()));
undo(b);
} catch (NoSuchElementException e) {}
return n;
}
public final long nextLong(long min, long max) {
long n = nextLong();
if (min <= n && n <= max) return n;
throw new NumberFormatException();
}
public final double nextDouble() {
StringBuilder sb = new StringBuilder();
byte b = readByte();
if (b == '-') {
sb.append(b);
b = readByte();
}
if (b == '0') {
sb.append(b);
b = readByte();
} else {
while (isNumber(b)) {
sb.append(b);
b = readByte();
}
}
if (b == '.') {
sb.append(b);
b = readByte();
while (isNumber(b)) {
sb.append(b);
b = readByte();
}
}
if (b == 'e' || b == 'E') {
sb.append(b);
b = readByte();
if (b == '-' || b == '+') {
sb.append(b);
b = readByte();
}
while (isNumber(b)) {
sb.append(b);
b = readByte();
}
}
undo(b);
return Double.parseDouble(sb.toString());
}
}
}