結果
| 問題 | No.3589 Make Ends Meet (Hard) |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-07-10 22:26:36 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 1,120 ms / 2,000 ms |
| コード長 | 22,576 bytes |
| 記録 | |
| コンパイル時間 | 4,258 ms |
| コンパイル使用メモリ | 109,480 KB |
| 実行使用メモリ | 162,964 KB |
| 最終ジャッジ日時 | 2026-07-10 22:26:59 |
| 合計ジャッジ時間 | 19,750 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 47 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.function.BiFunction;
import java.util.function.DoubleUnaryOperator;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
// new Main().test();
pw.flush();
}
void run() {
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
Fp fp = Fp.MOD998244353;
long mod = fp.modulus();
long[][][] dp = new long[N + 1][N + 1][((N * (N - 1)) / 2) + 1];// 決めた頂点数、最後の頂点数、y=(1+z)の次数
dp[1][1][0] = 1;
long[][][] f = new long[N + 1][N + 1][((N * (N - 1)) / 2) + 1];
for (int dist = 1; dist <= (N - 1); dist++) {
long[][][] ndp = new long[dp.length][dp[0].length][dp[0][0].length];
for (int k = 1; k < N; k++) {
// k頂点使った
for (int m = 1; m <= k; m++) {
// 最後m頂点
for (int j = 0; j <= ((k * (k - 1)) / 2); j++) {
// yの次数
if (dp[k][m][j] == 0) {
continue;
}
for (int l = 0; (k + l) <= N; l++) {
// 足す頂点数
int nk = k + l;
long way;
if (dist < K) {
way = fp.comb((N - k) - 1, l);
} else if (dist == K) {
way = fp.comb((N - k) - 1, l - 1);
} else {
way = fp.comb(N - k, l);
}
for (int o = 0; o <= l; ++o) {
ndp[nk][l][(j + ((l * (l - 1)) / 2)) + (o * m)] += fp.mul(fp.signedComb(l, l - o), way, dp[k][m][j]);
ndp[nk][l][(j + ((l * (l - 1)) / 2)) + (o * m)] %= mod;
}
}
}
}
}
dp = ndp;
if (dist >= K) {
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[i].length; j++) {
for (int k = 0; k < f[i][j].length; k++) {
f[i][j][k] += dp[i][j][k];
f[i][j][k] %= mod;
}
}
}
}
}
long ans = 0;
for (int n = 2; n <= N; n++) {
// 決めた頂点数、最後の頂点数、y=(1+z)の次数
for (int last = 1; last <= n; last++) {
for (int deg = 0; deg <= ((N * (N - 1)) / 2); deg++) {
ans += fp.mul(fp.comb(((int) (MathUtils.comb(N - n, 2))) + deg, ((N * (N - 1)) / 2) - M), f[n][last][deg]);
ans %= mod;
}
}
}
pw.println(ans);
}
}
class ArrayUtils {
public static void swap(long[] A, long[] B) {
if (A.length != B.length) {
throw new AssertionError();
}
for (int i = 0; i < A.length; i++) {
long tmp = A[i];
A[i] = B[i];
B[i] = tmp;
}
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
}
class Fp extends Zn implements LongFieldStrategy {
/**
* 998244353 を法とする有限体 F_998244353。
*/
public static final Fp MOD998244353 = new Fp(998244353);
public Fp(long mod) {
super(mod);
}
/**
* fac(n) 用に遅延初期化される階乗テーブル。
*/
int[] fac = new int[0];
/**
* ifac(n) 用に遅延初期化される逆階乗テーブル。
*/
int[] ifac = new int[0];
/**
* inv(n) 用に遅延初期化される逆元テーブル。
*/
int[] inv = new int[0];
public void expand(int n) {
fac = new int[n];
ifac = new int[n];
inv = new int[n];
Arrays.fill(fac, 1);
Arrays.fill(ifac, 1);
Arrays.fill(inv, 1);
for (int i = 2; i < n; ++i) {
fac[i] = ((int) ((i * (fac[i - 1] & 0xffffffffL)) % mod));
inv[i] = ((int) (mod - (((mod / i) * (inv[((int) (mod % i))] & 0xffffffffL)) % mod)));
ifac[i] = ((int) (((inv[i] & 0xffffffffL) * (ifac[i - 1] & 0xffffffffL)) % mod));
}
}
public long fac(int n) {
if (fac.length <= n) {
expand(Math.max(2 * fac.length, n + 1));
}
return fac[n] & 0xffffffffL;
}
public long ifac(int n) {
if (ifac.length <= n) {
expand(Math.max(2 * ifac.length, n + 1));
}
return ifac[n] & 0xffffffffL;
}
/**
* n < 0 でもok
*
* @param n
* @return */
public long inv(long n) {
if (n < 0) {
n = reduce(n);
}
return n < inv.length ? inv[((int) (n))] & 0xffffffffL : MathUtils.modInv(n, mod);
}
/**
* 事前条件: b != 0 in F_mod。返り値 r は r = a / b in F_mod。
* 未テスト
* 計算量: O(log mod)
*
* @param a
* 被除数
* @param b
* 除数
* @return a / b mod mod
*/
@Override
public long div(long a, long b) {
return mul(a, inv(b));
}
/**
* 事前条件: b != 0 in F_mod。返り値 r は r = 0。
* 未テスト
* 計算量: O(1)
*
* @param a
* 被除数
* @param b
* 除数
* @return 0
*/
@Override
public long mod(long a, long b) {
if (equals(b, zero())) {
throw new ArithmeticException("Division by zero");
}
return zero();
}
/**
* 返り値 r は a = 0 なら r = 0、そうでなければ r = 1。
* 未テスト
* 計算量: O(1)
*
* @param a
* 対象
* @return a のノルム
*/
@Override
public long norm(long a) {
return equals(a, zero()) ? 0 : 1;
}
/**
* 返り値 u は a = 0 なら u = 1、そうでなければ u = a。
* 未テスト
* 計算量: O(1)
*
* @param a
* 対象
* @return a = u * canonical(a) を満たす単元 u
*/
@Override
public long canonicalUnit(long a) {
if (equals(a, zero())) {
return one();
}
return a;
}
/**
* comb(0, 0)=1とする。
*
* @param n
* @param k
* @return */
public long comb(int n, int k) {
if ((k < 0) || ((n - k) < 0)) {
return 0;
}
return (((fac(n) * ifac(k)) % mod) * ifac(n - k)) % mod;
}
/**
* comb(n, k)(-1)^k
*
* @param n
* @param k
* @return */
public long signedComb(int n, int k) {
long ret = comb(n, k);
if (((k % 2) == 1) && (ret != 0)) {
ret = mod - ret;
}
return ret;
}
/**
* a は 32bit 整数を仮定
*/
public long pow(long a, long n) {
return MathUtils.modPow(a, n, mod);
}
}
/**
* primitive long に特化した可換環の代数的構造。
*/
interface LongCommutativeRingStrategy extends LongRingStrategy {}
/**
* primitive long に特化したユークリッド整域の代数的構造。
*/
interface LongEuclideanDomainStrategy extends LongGCDDomainStrategy {
/**
*
* @param a
* @param b
* @return a / b
*/
long div(long a, long b);
/**
*
* @param a
* @param b
* @return a % b
*/
long mod(long a, long b);
/**
*
* @param a
* @return a のノルム
*/
long norm(long a);
/**
* a = u * canonical(a) となる単元 u を返す。
*
* @param a
* @return 単元 u
*/
default long canonicalUnit(long a) {
return one();
}
@Override
default long gcd(long a, long b) {
while (!equals(b, zero())) {
a = mod(a, b);
long t = a;
a = b;
b = t;
}
if (equals(a, zero())) {
return a;
}
return div(a, canonicalUnit(a));
}
record ExtGCDResult(long x, long y, long gcd) {}
/**
* ax + by = gcd(a, b) を解く。
*
* @param a
* @param b
* @return 解 (x, y, gcd)
*/
default ExtGCDResult extgcd(long a, long b) {
long x0 = one();
long y0 = zero();
long g0 = a;
long x1 = zero();
long y1 = one();
long g1 = b;
while (!equals(g1, zero())) {
long q = div(g0, g1);
long nextG = sub(g0, mul(q, g1));
long nextX = sub(x0, mul(q, x1));
long nextY = sub(y0, mul(q, y1));
x0 = x1;
y0 = y1;
g0 = g1;
x1 = nextX;
y1 = nextY;
g1 = nextG;
}
if (equals(g0, zero())) {
return new ExtGCDResult(x0, y0, g0);
}
long u = canonicalUnit(g0);
return new ExtGCDResult(div(x0, u), div(y0, u), div(g0, u));
}
}
/**
* primitive long に特化した除法が可能な環の代数的構造。
*/
interface LongExactDivRingStrategy extends LongIntegralDomainStrategy {
/**
* 割り切れることが保証されている場合に a / b を計算する。
*
* @param a
* @param b
* @return a / b
*/
long divExact(long a, long b);
}
/**
* primitive long に特化した体の代数的構造。
*/
interface LongFieldStrategy extends LongEuclideanDomainStrategy , LongExactDivRingStrategy {
@Override
default long divExact(long a, long b) {
return div(a, b);
}
/**
*
* @param a
* @return a^-1
*/
long inv(long a);
/**
*
* @param a
* @param b
* @return a / b
*/
default long div(long a, long b) {
return mul(a, inv(b));
}
/**
* 1 + a + a^2 + ... = 1 / (1 - a) を計算する。
*
* @param a
* 公比
* @return 等比級数の和
*/
default long geometricSum(long a) {
return inv(sub(one(), a));
}
@Override
default LongEuclideanDomainStrategy.ExtGCDResult extgcd(long a, long b) {
if (!equals(a, zero())) {
return new LongEuclideanDomainStrategy.ExtGCDResult(inv(a), zero(), one());
} else if (!equals(b, zero())) {
return new LongEuclideanDomainStrategy.ExtGCDResult(zero(), inv(b), one());
} else {
return new LongEuclideanDomainStrategy.ExtGCDResult(zero(), zero(), zero());
}
}
}
/**
* primitive long に特化したGCD整域の代数的構造。
*/
interface LongGCDDomainStrategy extends LongIntegralDomainStrategy {
/**
*
* @param a
* @param b
* @return gcd(a, b)
*/
long gcd(long a, long b);
}
/**
* primitive long に特化した整域の代数的構造。
*/
interface LongIntegralDomainStrategy extends LongCommutativeRingStrategy {}
/**
* primitive long に特化した環の代数的構造。
*/
interface LongRingStrategy extends LongSemiRingStrategy {
/**
*
* @param a
* @return -a
*/
long neg(long a);
/**
*
* @param a
* @param b
* @return a - b
*/
default long sub(long a, long b) {
return add(a, neg(b));
}
}
/**
* primitive long に特化した半環の代数的構造。
*/
interface LongSemiRingStrategy {
/**
*
* @return 加法の単位元
*/
long zero();
/**
*
* @return 乗法の単位元
*/
long one();
/**
*
* @param a
* @param b
* @return a + b
*/
long add(long a, long b);
/**
*
* @param a
* @param b
* @return a * b
*/
long mul(long a, long b);
/**
*
* @param a
* @param b
* @return a == b
*/
boolean equals(long a, long b);
}
class MathUtils {
public static long modPow(long a, long n, long mod) {
if (n < 0) {
long inv = MathUtils.modInv(a, mod);
return MathUtils.modPow(inv, -n, mod);
}
if (n == 0) {
return 1;
}
return (MathUtils.modPow((a * a) % mod, n / 2, mod) * ((n % 2) == 1 ? a : 1)) % mod;
}
/**
* 拡張ユークリッドの互除法で逆元を求める。
*
* @param a
* @param mod
* @return */
public static long modInv(long a, long mod) {
a = ((a % mod) + mod) % mod;
long[] f0 = new long[]{ 1, 0, mod };
long[] f1 = new long[]{ 0, 1, a };
while (f1[2] != 0) {
long q = f0[2] / f1[2];
for (int i = 0; i < 3; i++) {
f0[i] -= q * f1[i];
}
ArrayUtils.swap(f0, f1);
}
return f0[1] < 0 ? mod + f0[1] : f0[1];
}
/**
* O(min(k, n-k))
* C(n,i)=C(n,i-1)(n-i+1)/iで計算
*
* @param n
* @param k
* @return */
public static long comb(int n, int k) {
if ((k < 0) || ((n - k) < 0)) {
return 0;
}
if (k > (n / 2)) {
return MathUtils.comb(n, n - k);
}
if (k == 0) {
return 1;
}
if (k == 1) {
return n;
}
if (k == 2) {
return ((1L * n) * (n - 1)) / 2;
}
if (k > (n - k)) {
return MathUtils.comb(n, n - k);
}
long ans = 1;
for (int i = 1; i <= k; i++) {
// C(n,i)=C(n,i-1)(n-i+1)/i
ans = (ans * ((n - i) + 1)) / i;
}
return ans;
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
}
class Zn implements LongCommutativeRingStrategy {
/**
* 剰余環 Z/modZ の法。
*/
final long mod;
public Zn(long mod) {
this.mod = mod;
}
public long modulus() {
return this.mod;
}
/**
* 返り値 r は r = 0。
* 未テスト
* 計算量: O(1)
*
* @return 0
*/
@Override
public long zero() {
return 0;
}
/**
* 返り値 r は r ≡ 1 (mod mod) かつ 0 ≤ r < mod。
* 未テスト
* 計算量: O(1)
*
* @return 1 mod mod
*/
@Override
public long one() {
return 1 % mod;
}
public long pow(long a, long n) {
if (n < 0) {
throw new AssertionError();
}
return MathUtils.modPow(a, n, mod);
}
@Override
public long add(long a, long b) {
long ret = (a + b) % mod;
if (ret < 0) {
ret += mod;
}
return ret;
}
public long sub(long a, long b) {
long ret = (a - b) % mod;
if (ret < 0) {
ret += mod;
}
return ret;
}
@Override
public long mul(long a, long b) {
return (a * b) % mod;
}
public long mul(long a, long b, long c) {
return (((a * b) % mod) * c) % mod;
}
/**
* 返り値 r は r ≡ -a (mod mod) かつ 0 ≤ r < mod。
* 未テスト
* 計算量: O(1)
*
* @param a
* 被減元
* @return -a mod mod
*/
@Override
public long neg(long a) {
return a == 0 ? 0 : mod - a;
}
/**
* 返り値 r は r ⇔ a = b。
* 未テスト
* 計算量: O(1)
*
* @param a
* 比較対象
* @param b
* 比較対象
* @return a == b
*/
@Override
public boolean equals(long a, long b) {
return a == b;
}
/**
* *
* 剰余を取り、0以上mod未満の値を返す。
*
* @param a
* @return */
public long reduce(long a) {
a %= mod;
if (a < 0) {
a += mod;
}
return a;
}
}
// --- Original Code ---
// import java.io.IOException;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.Fp;
// import library.util.MathUtils;
//
// public class Main {
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// // new Main().test();
// pw.flush();
// MergeFiles.export();
// }
//
// void run() {
// int N=sc.nextInt();
// int M=sc.nextInt();
// int K=sc.nextInt();
// Fp fp=Fp.MOD998244353;
// long mod=fp.modulus();
//
//
// long[][][] dp = new long[N + 1][N + 1][((N * (N - 1)) / 2) + 1];// 決めた頂点数、最後の頂点数、y=(1+z)の次数
//
// dp[1][1][0] = 1;
// long[][][]f=new long[N+1][N+1][N*(N-1)/2+1];
// for (int dist = 1; dist <= N-1; dist++) {
// long[][][]ndp=new long[dp.length][dp[0].length][dp[0][0].length];
// for (int k = 1; k < N; k++) {
// // k頂点使った
// for (int m = 1; m <= k; m++) {
// // 最後m頂点
// for (int j = 0; j <= ((k * (k - 1)) / 2); j++) {
// // yの次数
// if (dp[k][m][j] == 0) {
// continue;
// }
// for (int l = 0; (k + l) <= N; l++) {
// // 足す頂点数
// int nk = k + l;
// long way;
// if (dist < K) {
// way = fp.comb(N - k - 1, l);
// } else if (dist == K) {
// way = fp.comb(N - k - 1, l - 1);
// } else {
// way = fp.comb(N - k, l);
// }
// for (int o = 0; o <= l; ++o) {
// ndp[nk][l][(j + ((l * (l - 1)) / 2)) + (o * m)] += fp.mul(fp.signedComb(l, l - o), way, dp[k][m][j]);
// ndp[nk][l][(j + ((l * (l - 1)) / 2)) + (o * m)] %= mod;
// }
// }
// }
// }
// }
// dp=ndp;
// if (dist >= K) {
// for (int i = 0; i < f.length; i++) {
// for (int j = 0; j < f[i].length; j++) {
// for (int k = 0; k < f[i][j].length; k++) {
// f[i][j][k]+=dp[i][j][k];
// f[i][j][k]%=mod;
// }
// }
// }
// }
// }
// long ans=0;
// for (int n = 2; n <= N; n++) {
// // 決めた頂点数、最後の頂点数、y=(1+z)の次数
// for (int last = 1; last <= n; last++) {
// for (int deg = 0; deg <= ((N * (N - 1)) / 2); deg++) {
// ans += fp.mul(fp.comb((int)MathUtils.comb(N-n, 2) + deg, N*(N-1)/2-M), f[n][last][deg]);
// ans %= mod;
// }
// }
// }
// pw.println(ans);
// }
//
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//