結果
| 問題 | No.3584 Camouflage Mole |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-07-10 21:49:38 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 69 ms / 2,000 ms |
| コード長 | 16,947 bytes |
| 記録 | |
| コンパイル時間 | 4,050 ms |
| コンパイル使用メモリ | 110,968 KB |
| 実行使用メモリ | 45,624 KB |
| 最終ジャッジ日時 | 2026-07-10 21:49:46 |
| 合計ジャッジ時間 | 7,713 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
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();
Fp fp = Fp.MOD998244353;
long ans = fp.mul(fp.comb(N, 4), fp.pow(26, N - 4));
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;
}
/**
* 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];
}
}
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;
}
/**
* 返り値 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;
}
/**
* 返り値 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.ArrayUtils;
// import library.util.FloorSum;
// import library.util.Fp;
// import library.util.MathUtils;
// import library.util.fold.WaveletMatrix;
// import library.util.graph.Graphs;
// import library.util.graph.LongValueGraph;
// import library.util.polynomial.PolynomialFp2D.PartialFractionInYOfGeometricProduct;
// import library.util.polynomial.PolynomialFp;
// import library.util.polynomial.PolynomialFp2D;
// import library.util.polynomial.PolynomialFpDynamic;
// import library.util.polynomial.PolynomialFpDynamic2D;
// import library.util.polynomial.PolynomialFpDynamic3D;
// import library.util.segtree.SegTreeFactory;
// import library.util.seq.SortedArrays;
// import library.util.seq.WildcardMatcher;
//
// 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();
// Fp fp=Fp.MOD998244353;
// long ans=fp.mul(fp.comb(N, 4), fp.pow(26, N-4));
// pw.println(ans);
//
// }
//
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//