結果
| 問題 | No.3146 RE: Parentheses Counting |
| ユーザー |
 Nauclhlt🪷
|
| 提出日時 | 2025-03-02 15:02:59 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,842 bytes |
| コンパイル時間 | 8,712 ms |
| コンパイル使用メモリ | 169,388 KB |
| 実行使用メモリ | 72,612 KB |
| 最終ジャッジ日時 | 2025-05-16 20:51:44 |
| 合計ジャッジ時間 | 30,281 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | TLE * 1 |
| other | TLE * 28 -- * 15 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (119 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System.Numerics;
using System.Runtime.CompilerServices;
StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(writer);
Solver.Solve();
Console.Out.Flush();
public static class Solver
{
private static readonly AtCoderIO cin = new AtCoderIO();
public static unsafe void Solve()
{
ModFactorialCache cache = new(2000100);
int T = cin.Int();
while (T-- > 0)
{
int N = cin.Int();
if (N % 2 == 1)
{
Console.WriteLine(0);
}
else
{
N >>= 1;
N--;
ModInt ans = N == 0 ? 0 : ((ModInt)2L).Power(2 * N) - cache.Combination(2 * N + 1, N);
Console.WriteLine(ans.Raw());
}
}
}
}
// modintの階乗とその逆元を前計算して高速化.
// 前計算O(最大値). 階乗, 順列, 二項係数それぞれ定数時間.
// Depends on: ModInt
// @author Nauclhlt.
public sealed class ModFactorialCache
{
private ModInt[] _factorial;
private ModInt[] _inverseFactorial;
// 階乗とその逆元を前計算する.
// O(max)
public ModFactorialCache(long max)
{
_factorial = new ModInt[max + 1];
_inverseFactorial = new ModInt[max + 1];
_factorial[0] = 1;
_inverseFactorial[0] = ((ModInt)1).Inv();
for (long p = 1; p <= max; p++)
{
_factorial[p] = _factorial[p - 1] * p;
_inverseFactorial[p] = _inverseFactorial[p - 1] * ((ModInt)p).Inv();
}
}
// 二項係数nCrを計算する.
// O(1)
public ModInt Combination(long n, long r)
{
return _factorial[n] * (_inverseFactorial[n - r] * _inverseFactorial[r]);
}
// 順列の個数nPrを計算する.
// O(1)
public ModInt Permutation(long n, long r)
{
return _factorial[n] * _inverseFactorial[n - r];
}
// n!を計算する.
// O(1)
public ModInt Factorial(long n)
{
return _factorial[n];
}
}
static class Constants
{
public const long Mod = 998244353L;
//public const long Mod = 10007L;
//public const long Mod = 1000000007L;
}
public sealed class AtCoderIO
{
Queue<string> _readQueue = new Queue<string>();
private void LoadQueue()
{
if (_readQueue.Count > 0) return;
string line = Console.ReadLine();
string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
}
private void Guard()
{
if (_readQueue.Count == 0)
{
throw new Exception("NO DATA TO READ");
}
}
public int Int()
{
LoadQueue();
Guard();
return int.Parse(_readQueue.Dequeue());
}
public long Long()
{
LoadQueue();
Guard();
return long.Parse(_readQueue.Dequeue());
}
public string String()
{
LoadQueue();
Guard();
return _readQueue.Dequeue();
}
public short Short()
{
LoadQueue();
Guard();
return short.Parse(_readQueue.Dequeue());
}
public byte Byte()
{
LoadQueue();
Guard();
return byte.Parse(_readQueue.Dequeue());
}
public char Char()
{
LoadQueue();
Guard();
return char.Parse(_readQueue.Dequeue());
}
public double Double()
{
LoadQueue();
Guard();
return double.Parse(_readQueue.Dequeue());
}
public float Float()
{
LoadQueue();
Guard();
return float.Parse(_readQueue.Dequeue());
}
public ModInt ModInt()
{
return new ModInt(Long());
}
public T Read<T>()
{
Type type = typeof(T);
if (type == typeof(int)) return (T)(object)Int();
else if (type == typeof(long)) return (T)(object)Long();
else if (type == typeof(float)) return (T)(object)Float();
else if (type == typeof(double)) return (T)(object)Double();
else if (type == typeof(short)) return (T)(object)Short();
else if (type == typeof(byte)) return (T)(object)Byte();
else if (type == typeof(char)) return (T)(object)Char();
else if (type == typeof(string)) return (T)(object)String();
else if (type == typeof(ModInt)) return (T)(object)ModInt();
else return default(T);
}
public int[] IntArray(int n)
{
if (n == 0) return Array.Empty<int>();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = Int();
}
return arr;
}
public int[] ZeroIndexedPermutation(int n)
{
if (n == 0) return Array.Empty<int>();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = Int() - 1;
}
return arr;
}
public long[] LongArray(int n)
{
if (n == 0) return Array.Empty<long>();
long[] arr = new long[n];
for (int i = 0; i < n; i++)
{
arr[i] = Long();
}
return arr;
}
public double[] DoubleArray(int n)
{
if (n == 0) return Array.Empty<double>();
double[] arr = new double[n];
for (int i = 0; i < n; i++)
{
arr[i] = Double();
}
return arr;
}
public ModInt[] ModIntArray(int n)
{
if (n == 0) return Array.Empty<ModInt>();
ModInt[] arr = new ModInt[n];
for (int i = 0; i < n; i++)
{
arr[i] = (ModInt)Long();
}
return arr;
}
public T[] ReadArray<T>(int n)
{
if (n == 0) return Array.Empty<T>();
T[] arr = new T[n];
for (int i = 0; i < n; i++)
{
arr[i] = Read<T>();
}
return arr;
}
}
public readonly struct ModInt : IEquatable<ModInt>, IAdditionOperators<ModInt, ModInt, ModInt>, ISubtractionOperators<ModInt, ModInt, ModInt>, IAdditiveIdentity<ModInt, ModInt>
{
private readonly long Value;
public static ModInt One => (ModInt)1L;
public static ModInt Zero => (ModInt)0L;
public static ModInt AdditiveIdentity => Zero;
public ModInt(long value)
{
Value = SafeMod(value);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static long SafeMod(long a)
{
a %= Constants.Mod;
if (a < 0) a += Constants.Mod;
return a;
}
public ModInt Power(long exp)
{
if (exp <= -1) return this;
if (exp == 0) return 1;
if (exp == 1) return this;
ModInt m = Power(exp / 2);
m *= m;
if (exp % 2 == 1) m *= this;
return m;
}
public ModInt Inv()
{
return this.Power(Constants.Mod - 2L);
}
public static ModInt operator +(ModInt left, ModInt right)
{
return new ModInt(SafeMod(left.Value + right.Value));
}
public static ModInt operator -(ModInt left, ModInt right)
{
return new ModInt(SafeMod(left.Value - right.Value));
}
public static ModInt operator *(ModInt left, ModInt right)
{
return new ModInt(SafeMod(left.Value * right.Value));
}
public static ModInt operator /(ModInt left, ModInt right)
{
if (right.Value == 0L)
{
return Zero;
}
ModInt inv = right.Inv();
return SafeMod(left * inv);
}
public static ModInt operator %(ModInt left, ModInt right)
{
if (right.Value == 0L)
{
return Zero;
}
return new ModInt(SafeMod(left.Value % right.Value));
}
public static bool operator ==(ModInt left, ModInt right)
{
return left.Value == right.Value;
}
public static bool operator != (ModInt left, ModInt right)
{
return !(left == right);
}
public bool Equals(ModInt other)
{
return Value == other.Value;
}
public override bool Equals(object other)
{
if (other is ModInt m)
{
return this == m;
}
else return false;
}
public override int GetHashCode()
{
return Value.GetHashCode();
}
public static implicit operator ModInt(long v)
{
return new ModInt(v);
}
public static implicit operator ModInt(int v)
{
return new ModInt(v);
}
public static implicit operator long(ModInt m)
{
return m.Value;
}
public static implicit operator int(ModInt m)
{
return (int)m.Value;
}
public long Raw() => Value;
public override string ToString()
{
return Value.ToString();
}
}