結果
| 問題 |
No.2136 Dice Calendar?
|
| コンテスト | |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2022-10-15 20:15:04 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 19,917 bytes |
| コンパイル時間 | 3,801 ms |
| コンパイル使用メモリ | 92,992 KB |
| 実行使用メモリ | 326,796 KB |
| 最終ジャッジ日時 | 2024-06-26 20:17:39 |
| 合計ジャッジ時間 | 33,683 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 TLE * 1 -- * 5 |
ソースコード
package yukicoder_8614.solver6;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.NoSuchElementException;
public class Main {
public static void main(String[] args) {
new Main();
}
public Main() {
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 N = ic.nextInt(1, 20);
ic.readNewLine();
int[][] S = new int[N][6];
final int KIND = 9;
for (int i = 0; i < N; ++i) {
S[i][0] = ic.nextInt(1, KIND) - 1;
for (int j = 1; j < 6; ++j) {
ic.nextChar(' ');
S[i][j] = ic.nextInt(1, KIND) - 1;
}
ic.readNewLine();
}
ic.checkEOF();
long time = System.currentTimeMillis(), allTime = time;
final int MEET_IN_THE_MIDDLE = 2;
int lastChoose = Math.min(N, MEET_IN_THE_MIDDLE);
ArrayList<int[]> lastCreate = new ArrayList<>();
{
HashSet<Long> val = new HashSet<>();
enumerate(0, new int[KIND], val, Arrays.copyOfRange(S, N - lastChoose, N));
for (long v : val) {
int[] put = new int[lastChoose];
for (int i = 0;i < lastChoose;++ i) {
put[i] = (int)(v & 15);
v >>= 4;
}
lastCreate.add(put);
}
}
N -= lastChoose;
long[] factorial = new long[21];
factorial[0] = 1;
for (int i = 1; i < factorial.length; ++i) factorial[i] = factorial[i - 1] * i;
int[] max = new int[KIND];
for (int[] i : S) for (int j : i) ++max[j];
int[] remain = new int[KIND];
for (int i = KIND - 2; i >= 0; --i) remain[i] = remain[i + 1] + max[i + 1];
final int MOD = 998_244_353;
ArrayList<int[]> divide = new ArrayList<>();
for (int s = (1 << KIND - 1) - 1; s < 1 << N + KIND - 1;) {
// この時点のsは条件を満たした整数
divide.add(expansion(s, N, KIND));
int t = s | s - 1;
s = t + 1 | (~t & -~t) - 1 >> deBrujin32[(s & -s) * 0x077CB531 >>> 27] + 1;
}
System.err.println("partition: " + (System.currentTimeMillis() - time) + " ms (count:" + divide.size() + ")");
time = System.currentTimeMillis();
int source = N + KIND, sink = source + 1;
int gateVertex = N + 8;
MaxFlow flow = new MaxFlow(sink + gateVertex + 1);
for (int i = 0; i < N; ++i) {
flow.addEdge(source, i, 1);
for (int j = 0; j < 6; ++j) {
flow.addEdge(i, N + S[i][j], 1);
}
}
int[] sinkEdge = new int[KIND];
for (int i = 0; i < KIND; ++i) sinkEdge[i] = flow.addEdge(N + i, sink, 0);
int firstGate = flow.addEdge(source, sink + 1, 0);
for (int i = 1;i < gateVertex;++ i) flow.addEdge(sink + i, sink + i + 1, MaxFlow.INF);
int lastGate = flow.addEdge(sink + gateVertex, sink, 0);
long flowSum = 0;
ArrayList<int[]> goodPartition = new ArrayList<>(divide.size());
for (int[] partition : divide) {
boolean addFlow = true;
for (int i = 0; i < KIND; ++i) {
MaxFlow.CapEdge edge = flow.getEdge(sinkEdge[i]);
if (partition[i] >= edge.flow) { // 容量の方が大きい
flow.changeEdge(sinkEdge[i], partition[i], edge.flow);
}
}
for (int i = 0; i < KIND; ++i) {
MaxFlow.CapEdge edge = flow.getEdge(sinkEdge[i]);
if (partition[i] < edge.flow) { // 流し直し
long back = edge.flow - partition[i]; // 溢れる分
flow.changeEdge(firstGate, back, 0);
flow.changeEdge(lastGate, back, 0);
flow.changeEdge(sinkEdge[i], 0, 0);
flow.flow(edge.from, edge.to, back);
back = flow.getEdge(firstGate).flow;
flow.changeEdge(firstGate, 0, 0);
flow.changeEdge(lastGate, 0, 0);
flow.changeEdge(sinkEdge[i], partition[i], partition[i]);
if (back != 0) { // 戻す分が発生した
flowSum -= back;
addFlow = false;
}
}
}
if (flowSum != N && addFlow) flowSum += flow.flow(source, sink, N - flowSum);
if (flowSum != N) continue;
goodPartition.add(partition);
}
System.err.println("flow: " + (System.currentTimeMillis() - time) + " ms (" + "create:" + goodPartition.size() + ")");
time = System.currentTimeMillis();
BitSet createPartition = new BitSet(1 << N + lastChoose + KIND - 1);
int[] sb = new int[KIND];
for (int[] partition : goodPartition) {
int bit = compress(partition, N);
for (int i = KIND - 2;i >= 0;-- i) sb[i] = sb[i + 1] + partition[i + 1] + 1;
for (int[] add : lastCreate) {
int next = bit;
for (int i : add) {
int mask = next & (1 << sb[i]) - 1;
next = (next & ~mask) << 1 | next & mask;
}
createPartition.set(next);
}
}
System.err.println("merge: " + (System.currentTimeMillis() - time) + " ms");
time = System.currentTimeMillis();
long ans = 0;
for (int partition = createPartition.nextSetBit(0);partition >= 0;partition = createPartition.nextSetBit(partition + 1)) {
long multichoose = factorial[N + lastChoose];
for (int i : expansion(partition, N + lastChoose, KIND)) multichoose /= factorial[i];
ans += multichoose % MOD;
}
ans %= MOD;
out.println(ans);
System.err.println("multichoose: " + (System.currentTimeMillis() - time) + " ms");
time = System.currentTimeMillis();
System.err.println("all: " + (System.currentTimeMillis() - allTime) + " ms");
}
public static void enumerate(int number, int[] create, HashSet<Long> set, int[]... S) {
if (number == S.length) {
long put = 0;
for (int i = create.length - 1;i >= 0;-- i) {
for (int j = 0;j < create[i];++ j) {
put <<= 4;
put |= i;
}
}
set.add(put);
return;
}
for (int i : S[number]) {
++ create[i];
enumerate(number + 1, create, set, S);
-- create[i];
}
}
static final int[] deBrujin32 = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7,
26, 12, 18, 6, 11, 5, 10, 9 };
public static int compress(int[] partition, int N) {
int put = 0;
for (int i : partition) {
put <<= 1;
put |= 1;
put <<= i;
}
return put;
}
public static int[] expansion(int partition, int N, int KIND) {
int[] put = new int[KIND];
int lastCtz = 0;
for (int i = put.length - 1;i != 0;-- i) {
put[i] = deBrujin32[(partition & -partition) * 0x077CB531 >>> 27];
partition ^= 1 << put[i];
put[i] -= lastCtz;
lastCtz += put[i] + 1;
}
put[0] = N + KIND - 1 - lastCtz;
return put;
}
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 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());
}
}
}
class MaxFlow {
private static final class InternalCapEdge {
final int to;
final int rev;
long cap;
InternalCapEdge(int to, int rev, long cap) {
this.to = to;
this.rev = rev;
this.cap = cap;
}
}
public static final class CapEdge {
public final int from, to;
public final long cap, flow;
CapEdge(int from, int to, long cap, long flow) {
this.from = from;
this.to = to;
this.cap = cap;
this.flow = flow;
}
@Override
public boolean equals(Object o) {
if (o instanceof CapEdge) {
CapEdge e = (CapEdge) o;
return from == e.from && to == e.to && cap == e.cap && flow == e.flow;
}
return false;
}
}
private static final class IntPair {
final int first, second;
IntPair(int first, int second) {
this.first = first;
this.second = second;
}
}
static final long INF = Long.MAX_VALUE;
private final int n;
private final java.util.ArrayList<IntPair> pos;
private final java.util.ArrayList<InternalCapEdge>[] g;
@SuppressWarnings("unchecked")
public MaxFlow(int n) {
this.n = n;
pos = new java.util.ArrayList<>();
g = new java.util.ArrayList[n];
for (int i = 0; i < n; i++) {
g[i] = new java.util.ArrayList<>();
}
}
public int addEdge(int from, int to, long cap) {
rangeCheck(from, 0, n);
rangeCheck(to, 0, n);
nonNegativeCheck(cap, "Capacity");
int m = pos.size();
pos.add(new IntPair(from, g[from].size()));
int fromId = g[from].size();
int toId = g[to].size();
if (from == to) toId++;
g[from].add(new InternalCapEdge(to, toId, cap));
g[to].add(new InternalCapEdge(from, fromId, 0L));
return m;
}
private InternalCapEdge getInternalEdge(int i) {
return g[pos.get(i).first].get(pos.get(i).second);
}
private InternalCapEdge getInternalEdgeReversed(InternalCapEdge e) {
return g[e.to].get(e.rev);
}
public CapEdge getEdge(int i) {
int m = pos.size();
rangeCheck(i, 0, m);
InternalCapEdge e = getInternalEdge(i);
InternalCapEdge re = getInternalEdgeReversed(e);
return new CapEdge(re.to, e.to, e.cap + re.cap, re.cap);
}
public CapEdge[] getEdges() {
CapEdge[] res = new CapEdge[pos.size()];
java.util.Arrays.setAll(res, this::getEdge);
return res;
}
public void changeEdge(int i, long newCap, long newFlow) {
int m = pos.size();
rangeCheck(i, 0, m);
nonNegativeCheck(newCap, "Capacity");
if (newFlow > newCap) {
throw new IllegalArgumentException(
String.format("Flow %d is greater than the capacity %d.", newCap, newFlow));
}
InternalCapEdge e = getInternalEdge(i);
InternalCapEdge re = getInternalEdgeReversed(e);
e.cap = newCap - newFlow;
re.cap = newFlow;
}
public long maxFlow(int s, int t) {
return flow(s, t, INF);
}
public long maxFlow_fordFulkerson(int s, int t) {
return flow_fordFulkerson(s, t, INF);
}
public long flow(int s, int t, long flowLimit) {
rangeCheck(s, 0, n);
rangeCheck(t, 0, n);
long flow = 0L;
int[] level = new int[n];
int[] que = new int[n];
int[] iter = new int[n];
while (flow < flowLimit) {
bfs(s, t, level, que);
if (level[t] < 0) break;
java.util.Arrays.fill(iter, 0);
while (flow < flowLimit) {
long d = dfs(t, s, flowLimit - flow, iter, level);
if (d == 0) break;
flow += d;
}
}
return flow;
}
private int[] fordFulkersonDFSCheck;
private int fordFulkersonDFSCheckNumber;
public long flow_fordFulkerson(int s, int t, long flowLimit) {
rangeCheck(s, 0, n);
rangeCheck(t, 0, n);
if (fordFulkersonDFSCheck == null) {
fordFulkersonDFSCheck = new int[n];
fordFulkersonDFSCheckNumber = 0;
}
long flow = 0;
while(flow < flowLimit) {
++ fordFulkersonDFSCheckNumber;
fordFulkersonDFSCheck[s] = fordFulkersonDFSCheckNumber;
long nowFlow = dfs_fordFulkerson(s, t, flowLimit - flow, fordFulkersonDFSCheckNumber);
if (nowFlow == 0) return flow;
flow += nowFlow;
}
return flow;
}
private long dfs_fordFulkerson(int s, int t, long flowLimit, int checkNumber) {
if (s == t) return flowLimit;
long sum = 0;
for (InternalCapEdge e : g[s]) {
if (e.cap == 0 || fordFulkersonDFSCheck[e.to] == checkNumber) continue;
fordFulkersonDFSCheck[e.to] = checkNumber;
long flow = dfs_fordFulkerson(e.to, t, Math.min(flowLimit, e.cap), checkNumber);
sum += flow;
e.cap -= flow;
getInternalEdgeReversed(e).cap += flow;
}
return sum;
}
private void bfs(int s, int t, int[] level, int[] que) {
java.util.Arrays.fill(level, -1);
int hd = 0, tl = 0;
que[tl++] = s;
level[s] = 0;
while (hd < tl) {
int u = que[hd++];
for (InternalCapEdge e : g[u]) {
int v = e.to;
if (e.cap == 0 || level[v] >= 0) continue;
level[v] = level[u] + 1;
if (v == t) return;
que[tl++] = v;
}
}
}
private long dfs(int cur, int s, long flowLimit, int[] iter, int[] level) {
if (cur == s) return flowLimit;
long res = 0;
int curLevel = level[cur];
for (int itMax = g[cur].size(); iter[cur] < itMax; iter[cur]++) {
int i = iter[cur];
InternalCapEdge e = g[cur].get(i);
InternalCapEdge re = getInternalEdgeReversed(e);
if (curLevel <= level[e.to] || re.cap == 0) continue;
long d = dfs(e.to, s, Math.min(flowLimit - res, re.cap), iter, level);
if (d <= 0) continue;
e.cap += d;
re.cap -= d;
res += d;
if (res == flowLimit) break;
}
return res;
}
public boolean[] minCut(int s) {
rangeCheck(s, 0, n);
boolean[] visited = new boolean[n];
int[] stack = new int[n];
int ptr = 0;
stack[ptr++] = s;
visited[s] = true;
while (ptr > 0) {
int u = stack[--ptr];
for (InternalCapEdge e : g[u]) {
int v = e.to;
if (e.cap > 0 && !visited[v]) {
visited[v] = true;
stack[ptr++] = v;
}
}
}
return visited;
}
private void rangeCheck(int i, int minInclusive, int maxExclusive) {
if (i < 0 || i >= maxExclusive) {
throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, maxExclusive));
}
}
private void nonNegativeCheck(long cap, String attribute) {
if (cap < 0) { throw new IllegalArgumentException(String.format("%s %d is negative.", attribute, cap)); }
}
}