結果
| 問題 | No.3753 Certainly a Cretan |
| コンテスト | |
| ユーザー |
 tobisatis
|
| 提出日時 | 2026-10-03 18:25:40 |
| 言語 | C# (.NET 10.0.402 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 8,734 bytes |
| 記録 | |
| コンパイル時間 | 15,284 ms |
| コンパイル使用メモリ | 173,684 KB |
| 実行使用メモリ | 154,212 KB |
| 最終ジャッジ日時 | 2026-10-03 18:26:34 |
| 合計ジャッジ時間 | 34,657 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 WA * 39 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (227 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net10.0/main.dll main -> /home/judge/data/code/bin/Release/net10.0/publish/
ソースコード
#nullable enable
#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries), 0);
return T.Parse(_input[_iter++], null);
}
#endregion
var u0 = new SegmentTreeRLEOperation.Node(0, 1);
var u1 = new SegmentTreeRLEOperation.Node(1, 1);
var n = I<int>();
var init = new SegmentTreeRLEOperation.Node[n];
init.AsSpan().Fill(u0);
var data = new SegmentTree<SegmentTreeRLEOperation.Node, SegmentTreeRLEOperation.Operator>(init);
void U(int i, int f) => data.Set(i, f == 1 ? u1 : u0);
ModInt Q(int k)
{
var prod = data.Product(0, n);
var (rc, r) = (prod.RC, prod.R);
prod = data.Product(0, n - r);
var j = k - (n - r) / 2;
return prod.TotalProduct * SegmentTreeRLEOperation.G(r, rc == 0 ? r - j : j);
}
var q = I<int>();
{
var s = I<string>();
for (var i = 0; i < n; i++) if (s[i] == 'Y') U(i, 1);
}
var ans = new List<ModInt>();
while (q-- > 0)
{
var t = I<int>();
var a = I<int>();
if (t == 1) U(a - 1, data.Product(a - 1, a).LC ^ 1);
else ans.Add(Q(a));
}
Console.WriteLine(string.Join(Environment.NewLine, ans));
readonly record struct ModInt
{
public const uint Mod = 998244353;
readonly uint _v;
public ModInt(long value)
{
var v = value % Mod;
if (v < 0) v += Mod;
_v = (uint)v;
}
public static ModInt Unsafe(uint value) => new(value, true);
ModInt(uint value, bool _) { _v = value; }
public static implicit operator ModInt(long v) => new(v);
public static explicit operator int(ModInt modInt) => (int)modInt._v;
public static ModInt AdditiveIdentity => new(0, true);
public static ModInt operator +(ModInt a, ModInt b)
{
var v = a._v + b._v;
if (v >= Mod) v -= Mod;
return new(v, true);
}
public ModInt AdditiveInverse()
{
if (_v == 0) return AdditiveIdentity;
return new(Mod - _v, true);
}
public static ModInt operator -(ModInt a, ModInt b) => a + b.AdditiveInverse();
public static ModInt MultiplicativeIdentity => new(1, true);
public static ModInt operator *(ModInt a, ModInt b) => new((uint)((ulong)a._v * b._v % Mod), true);
public ModInt MultiplicativeInverse() => _v == 0 ? throw new DivideByZeroException() : Power(_v, Mod - 2);
public static ModInt operator /(ModInt a, ModInt b) => a * b.MultiplicativeInverse();
static uint Power(ulong v, long p)
{
var (res, k) = (1UL, v);
while (p > 0)
{
if ((p & 1) > 0) res = res * k % Mod;
k = k * k % Mod;
p >>= 1;
}
return (uint)res;
}
public ModInt Power(long p) => p < 0 ? MultiplicativeInverse().Power(-p) : Power(_v, p);
public override string ToString() => _v.ToString();
}
static class FactorialExtensions
{
public static ModInt Factorial(this int value)
{
Extend(value);
return value < 0 ? _inv[-value] : _fac[value];
}
public static ModInt P(this int n, int r)
{
if (r < 0 || r > n) return 0;
if (n <= MaxN) return Factorial(n) * Factorial(r - n);
ModInt res = 1;
for (var i = 0; i < r; i++) res *= n - i;
return res;
}
public static ModInt C(this int n, int r)
{
if (r < 0 || r > n) return 0;
r = Math.Min(r, n - r);
return P(n, r) * Factorial(-r);
}
public static ModInt H(this int n, int r) => C(r + n - 1, r);
public static ModInt ModIntPower(this int value, long power) => ((ModInt)value).Power(power);
public static ModInt ModIntInverse(this int n)
{
if (n == 0) throw new DivideByZeroException();
if (n < 0) return ModIntInverse(-n).AdditiveInverse();
if (n > MaxN) return ((ModInt)n).MultiplicativeInverse();
return Factorial(n - 1) * Factorial(-n);
}
const int MaxN = (1 << 24) - 1;
static ModInt[] _fac = [1];
static ModInt[] _inv = [1];
static void Extend(int q)
{
var l = _fac.Length;
if (q < 0) q = -q;
if (q < l || MaxN < q) return;
while (l <= q) l <<= 1;
var fac = new ModInt[l];
var inv = new ModInt[l];
fac[0] = 1;
for (var i = 1; i < fac.Length; i++) fac[i] = fac[i - 1] * ModInt.Unsafe((uint)i);
inv[l - 1] = fac[l - 1].Power(-1);
for (var i = inv.Length - 1; i > 0; i--) inv[i - 1] = inv[i] * ModInt.Unsafe((uint)i);
(_fac, _inv) = (fac, inv);
}
}
interface ISegmentTreeOperator<TMonoid>
{
TMonoid IdentityElement { get; }
TMonoid Operation(TMonoid x, TMonoid y);
}
class SegmentTree<TMonoid, TOperator> where TOperator : struct, ISegmentTreeOperator<TMonoid>
{
public int BaseSize { get; protected init; }
protected int Height { get; init; }
protected TOperator Op { get; init; }
protected TMonoid[] Values { get; init; }
public SegmentTree(TMonoid[] initial, TOperator op = default)
{
Op = op;
(BaseSize, Height) = (1, 0);
while (BaseSize < initial.Length) (BaseSize, Height) = (BaseSize << 1, Height + 1);
var size = BaseSize << 1;
Values = new TMonoid[size];
var values = Values;
for (var i = 0; i < size; i++) values[i] = op.IdentityElement;
for (var i = 0; i < initial.Length; i++) values[i + BaseSize] = initial[i];
for (var i = BaseSize - 1; i > 0; i--) Update(values, i);
}
public TMonoid Product(int l, int r)
{
(l, r) = (l + BaseSize, r + BaseSize);
var (resL, resR) = (Op.IdentityElement, Op.IdentityElement);
var values = Values;
while (l < r)
{
if ((l & 1) == 1) resL = Op.Operation(resL, values[l++]);
if ((r & 1) == 1) resR = Op.Operation(values[--r], resR);
(l, r) = (l >> 1, r >> 1);
}
return Op.Operation(resL, resR);
}
public void Set(int index, TMonoid value)
{
var j = index + BaseSize;
var values = Values;
values[j] = value;
while ((j >>= 1) > 0) Update(values, j);
}
protected void Update(TMonoid[] values, int k) { values[k] = Op.Operation(values[k << 1], values[(k << 1) + 1]); }
}
static class SegmentTreeRLEOperation
{
public static ModInt G(int n, int k) => n.C(k) - n.C(k - 1);
public static ModInt F(int n = 0) => n % 2 == 0 ? G(n, n / 2) : 0;
public static ModInt F(ModInt l, ModInt r) => l * r;
public static ModInt F(int l, ModInt m, int r) => F(F(F(l), m), F(r));
public readonly struct Node
{
public bool IsEmpty { get; }
public bool IsAllSame { get; }
public int LC { get; }
public int L { get; }
public int RC { get; }
public int R { get; }
public ModInt M { get; }
public Node()
{
IsEmpty = true;
M = F();
}
public Node(int c, int len)
{
IsEmpty = false;
IsAllSame = true;
LC = RC = c;
L = R = len;
M = F();
}
Node(int lc, int l, int rc, int r, ModInt m)
{
IsEmpty = IsAllSame = false;
LC = lc;
L = l;
RC = rc;
R = r;
M = m;
}
public ModInt TotalProduct
{
get
{
if (IsEmpty) return F();
if (IsAllSame) return F(L);
return F(L, M, R);
}
}
public static Node Merge(Node x, Node y)
{
if (x.IsEmpty) return y;
if (y.IsEmpty) return x;
if (x.IsAllSame && y.IsAllSame)
{
if (x.LC == y.LC) return new(x.LC, x.L + y.L);
return new(x.LC, x.L, y.RC, y.R, F());
}
if (x.IsAllSame)
{
if (x.LC == y.LC) return new(x.LC, x.L + y.L, y.RC, y.R, y.M);
return new(x.LC, x.L, y.RC, y.R, F(y.L, y.M, 0));
}
if (y.IsAllSame)
{
if (x.RC == y.LC) return new(x.LC, x.L, y.RC, x.R + y.L, x.M);
return new(x.LC, x.L, y.RC, y.R, F(0, x.M, x.R));
}
if (x.RC == y.LC) return new(x.LC, x.L, y.RC, y.R, F(F(x.M, F(x.R + y.L)), y.M));
return new(x.LC, x.L, y.RC, y.R, F(F(x.M, F(x.R)), F(F(y.L), y.M)));
}
}
public readonly struct Operator : ISegmentTreeOperator<Node>
{
public Node IdentityElement => new();
public Node Operation(Node x, Node y) => Node.Merge(x, y);
}
}