#1191360 (C#) No.3753 Certainly a Cretan

• 問題: No.3753 Certainly a Cretan
• ユーザー: tobisatis
• 提出日時: 2026-10-03 18:34:02
• 言語: C# (.NET 10.0.402 + ACL)
• 結果: AC
• 実行時間: 2,250 ms / 2,500 ms
• コード長: 8,817 bytes
• コンパイル時間: 10,045 ms
• コンパイル使用メモリ: 171,352 KB
• 実行使用メモリ: 152,184 KB
• 最終ジャッジ日時: 2026-10-03 18:34:31
• 合計ジャッジ時間: 26,572 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 2
other	AC * 46

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (257 ミリ秒)。
  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)
    {
        if (n == 0) return 1;
        if (k > n / 2) return 0;
        return 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);
    }

}