結果

問題 No.2219 Re:010
コンテスト
ユーザー Lisp_Coder
提出日時 2023-04-20 16:01:37
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,804 bytes
コンパイル時間 870 ms
コンパイル使用メモリ 108,672 KB
実行使用メモリ 23,552 KB
最終ジャッジ日時 2024-10-15 13:36:19
合計ジャッジ時間 4,591 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;
using System.Collections.Generic;

class Scanner<T>
{
    readonly Func<string, T> parse;
    readonly char[] separator = new[] { ' ' };
    private readonly Queue<T> buffer = new Queue<T>();

    public Scanner(Func<string, T> parse)
    {
        this.parse = parse;
    }

    public T Next()
    {
        if (buffer.Count != 0) return buffer.Dequeue();

        string[] inputs = Console.ReadLine().Split(separator, StringSplitOptions.RemoveEmptyEntries);
        foreach (var input in inputs)
        {
            buffer.Enqueue(parse(input));
        }

        return buffer.Dequeue();
    }

    public T[] Next(int n)
    {
        var result = new T[n];
        for (int i = 0; i < n; i++)
        {
            result[i] = Next();
        }
        return result;
    }

    public List<T> NextList(int n)
    {
        var result = new List<T>();
        for (int i = 0; i < n; i++)
        {
            result.Add(Next());
        }
        return result;
    }
}

class Program
{
    static void Main()
    {
        const int MOD = 998244353;
        Scanner<string> sc = new Scanner<string>(s => s);
        string st = sc.Next();
        int n = st.Length;
        int q = st.Count(c => c == '?');

        long ans = 0;
        for (int i = 0; i < (1 << q); i++)
        {
            char[] t = st.ToCharArray();
            for (int j = 0; j < q; j++)
            {
                if (((i >> j) & 1) == 0)
                {
                    t[GetIndexOfQuestionMark(st, j)] = '0';
                }
                else
                {
                    t[GetIndexOfQuestionMark(st, j)] = '1';
                }
            }
            string sPrime = new string(t);
            ans = (ans + Count010Substrings(sPrime)) % MOD;
        }
        Console.WriteLine(ans);
    }

    static int GetIndexOfQuestionMark(string s, int qIndex)
    {
        int count = -1;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '?')
            {
                count++;
                if (count == qIndex)
                {
                    return i;
                }
            }
        }
        return -1;
    }

    static long Count010Substrings(string s)
    {
        int n = s.Length;
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            preSum[i] = preSum[i - 1] + (s[i - 1] == '0' ? 1 : 0);
        }
        long ans = 0;
        int num10 = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == '1')
            {
                num10 += preSum[n] - preSum[i + 1];
            }
            else if (s[i] == '0')
            {
                ans += num10;
            }
        }
        return ans;
    }
}
0