結果

問題 No.1403 調和の魔法陣
ユーザー CuriousFairy315CuriousFairy315
提出日時 2020-08-21 05:54:03
言語 Java21
(openjdk 21)
結果
AC  
実行時間 708 ms / 3,153 ms
コード長 12,587 bytes
コンパイル時間 3,050 ms
コンパイル使用メモリ 90,900 KB
実行使用メモリ 69,428 KB
最終ジャッジ日時 2023-10-17 23:14:23
合計ジャッジ時間 17,112 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 231 ms
65,248 KB
testcase_01 AC 232 ms
65,324 KB
testcase_02 AC 232 ms
65,236 KB
testcase_03 AC 267 ms
65,964 KB
testcase_04 AC 304 ms
65,908 KB
testcase_05 AC 324 ms
65,600 KB
testcase_06 AC 644 ms
69,428 KB
testcase_07 AC 517 ms
65,892 KB
testcase_08 AC 563 ms
65,840 KB
testcase_09 AC 562 ms
65,836 KB
testcase_10 AC 590 ms
65,820 KB
testcase_11 AC 551 ms
65,924 KB
testcase_12 AC 551 ms
65,924 KB
testcase_13 AC 523 ms
65,888 KB
testcase_14 AC 462 ms
66,128 KB
testcase_15 AC 549 ms
65,916 KB
testcase_16 AC 579 ms
66,216 KB
testcase_17 AC 562 ms
65,828 KB
testcase_18 AC 566 ms
65,924 KB
testcase_19 AC 566 ms
66,156 KB
testcase_20 AC 708 ms
68,180 KB
testcase_21 AC 699 ms
68,232 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder_4596;

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.BitSet;
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();
		ic.checkEOF();
	}

	public void solve(InputChecker ic, java.io.PrintWriter out) {

		int T = ic.nextInt(1, 10000);
		ic.readNewLine();
		final int MOD = 998_244_353;
		final int N = 10;
		final int MAX_LENGTH = 600;

		int[][] pow = new int[(N + 1) * (N + 1)][MAX_LENGTH + 1];
		for (int i = 0;i < pow.length;++ i) for (int j = 0;j < pow[i].length;++ j) pow[i][j] = pow(i, j, MOD);
		int[][] comb = new int[N][(MAX_LENGTH + 1) / 3 + 1];
		for (int i = 0;i < N;++ i) for (int j = 0;j < comb[i].length;++ j) {
			int tmp = 0;
			tmp = add(tmp, pow[i + 1][j], MOD);
			tmp = sub(tmp, add(pow[i][j], pow[i][j], MOD), MOD);
			tmp = add(tmp, pow[Math.max(0, i - 1)][j], MOD);
			comb[i][j] = tmp;
		}

		int[][] twoAns = new int[4 * (N - 1) + 1][(MAX_LENGTH + 1) / 3 + 1];
		{
			for (int i = 0;i < twoAns.length;++ i) {
				final int Nd = N - 1;
				for (int j = 0;j <= 2 * Nd;++ j) {
					int d1 = calc12(j, N, MOD);
					int d2 = calc12(i - j, N, MOD);
					if (d1 == 0 || d2 == 0) continue;
					for (int k = 0;k < twoAns[i].length;++ k) twoAns[i][k] = add(twoAns[i][k], pow(mul(d1, d2, MOD), k, MOD), MOD);
				}
			}
		}

		ArrayList<ArrayList<Tuple>> ans = new ArrayList<>((N - 1) * 4 + 1);
		{
			final int MAX_X = (N - 1) * 4;
			final int Nd = N - 1;
			for (int i = 0;i <= MAX_X;++ i) ans.add(new ArrayList<>());
			int[][][][][] calc = new int[MAX_X + 1][N][N][N][N];
			for (int a = 0;a < N;++ a) {
				for (Range w1 : range(0, N)) {
					for (Range w2 : range(0, N)) {
						for (int x = 0;x <= MAX_X;++ x) {
							int h1min = Math.max(Math.max(0, x - a - w1.l - Nd), w2.r - a);
							int h1max = Math.min(Math.min(Nd, x - a - w1.r), Nd - a + w2.l);
							int h2min = Math.max(Math.max(0, a + w1.r - Nd), a - w2.l);
							int h2max = Math.min(Math.min(Nd, a + w1.l), Nd + a - w2.r);
							if (h1max - h1min < 0 || h2max - h2min < 0) continue;
							++ calc[x][w1.r - w1.l][w2.r - w2.l][h1max - h1min][h2max - h2min];
						}
					}
				}
			}
			for (int x = 0;x <= MAX_X;++ x) {
				for (int wl = 0;wl < N;++ wl) {
					for (int wr = 0;wr < N;++ wr) {
						int[] h = new int[(N + 1) * (N + 1)];
						for (int hl = 0;hl < N;++ hl) {
							for (int hr = 0;hr < N;++ hr) {
								h[(hl + 1) * (hr + 1)] += calc[x][wl][wr][hl][hr] * (hl + 1);
							}
						}
						for (int i = 0;i < h.length;++ i) {
							if (h[i] > 0) ans.get(x).add(new Tuple(wl, wr, i, h[i]));
						}
					}
				}
				ans.get(x).trimToSize();
			}
		}

		for (int i = 0;i < T;++ i) {
			int W = ic.nextInt(1, 600);
			ic.nextChar(' ');
			int H = ic.nextInt(1, 600);
			ic.nextChar(' ');
			int X = ic.nextInt(0, 81);
			ic.readNewLine();
			int w = (W + 2) / 3, h = (H + 2) / 3;

			if (W % 3 != 2) {
				if (H % 3 != 2) {
					out.println(solve11(w, h, X, N, MOD));
				} else {
					out.println(solve12(w, h, X, N, MOD));
				}
			} else {
				if (H % 3 != 2) {
					out.println(solve21(w, h, X, N, MOD));
				} else {
					if (w == 1) {
						out.println(X < twoAns.length ? twoAns[X][h] : 0);
					} else if (h == 1) {
						out.println(X < twoAns.length ? twoAns[X][w] : 0);
					} else {
						if (X < ans.size()) {
							int sum = 0;
							for (Tuple t : ans.get(X)) {
								int tmp = t.num;
								tmp = mul(tmp, comb[t.width1][w], MOD);
								tmp = mul(tmp, comb[t.width2][w - 1], MOD);
								tmp = mul(tmp, pow[t.height][h - 1], MOD);
								sum = add(sum, tmp, MOD);
							}
							out.println(sum);
						} else {
							out.println(0);
						}
					}
				}
			}
		}
	}

	class Range {
		final int l, r;
		Range(int l, int r) {
			this.l = l;
			this.r = r;
		}
	}

	private Range[] range(int begin, int end) {
		Range[] ret = new Range[(end - begin) * (end - begin + 1) / 2];
		int i = 0;
		for (int l = begin;l < end;++ l) {
			for (int r = l;r < end;++ r) {
				ret[i++] = new Range(l, r);
			}
		}
		return ret;
	}

	class Tuple {
		final int width1, width2, height;
		final int num;
		Tuple(int w1, int w2, int h, int n) {
			width1 = w1;
			width2 = w2;
			height = h;
			num = n;
		}
		@Override
		public String toString() {
			return "(" + width1 + "," + width2 + "," + height + " : " + num + ")";
		}
	}

	private static int solve11(final int w, final int h, final int X, final int N, final int mod) {
		return X < N ? 1 : 0;
	}

	private static int calc12(int X, int N, int mod) {
		return Math.max(0, N - Math.abs(N - 1 - X));
	}

	private static int solve12(int w, int h, int X, int N, int mod) {
		return pow(calc12(X, N, mod), w, mod);
	}

	private static int solve21(final int w, final int h, final int X, final int N, final int mod) {
		return solve12(h, w, X, N, mod);
	}

	public static boolean isRanged(int n, int l, int r) {
		return l <= n && n <= r;
	}
	public static int pow(int a, int b, int mod) {
		if (b < 0) b = b % (mod - 1) + mod - 1;
		long ans = 1;
		for (long mul = a;b > 0;b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod;
		return (int)ans;
	}

	public static int add(int a, int b, int mod) {
		int ret = a + b;
		if (ret >= mod) ret -= mod;
		return ret;
	}

	public static int sub(int a, int b, int mod) {
		int ret = a - b;
		if (ret < 0) ret += mod;
		return ret;
	}

	public static int mul(int a, int b, int mod) {
		return (int)((long)a * b % mod);
	}

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