結果

問題 No.2219 Re:010
コンテスト
ユーザー Lisp_Coder
提出日時 2023-04-20 15:43:21
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,470 bytes
コンパイル時間 897 ms
コンパイル使用メモリ 105,728 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2024-10-15 13:24:39
合計ジャッジ時間 4,860 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 Internal;
using System.Collections.Generic;
using System.Text;

class Scanner
{
    string[] s;
    int i;
    char[] cs = new char[] { ' ' };
    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string Next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Next();
        i = 0;
        return s[i++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    public ulong NextUlong()
    {
        return ulong.Parse(Next());
    }

    public decimal NextDecimal()
    {
        return decimal.Parse(Next());
    }

    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextInt() + add;
        }
        return Array;
    }

    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextDouble() + add;
        }
        return Array;
    }

    public long[] ArrayLong(long N, long add = 0)
    {
        long[] Array = new long[N];
        for (long i = 0; i < N; i++)
        {
            Array[i] = NextLong() + add;
        }
        return Array;
    }
}

class Program
{
    static void Main()
    {
        const int MOD = 998244353;
        Scanner sc = new Scanner();

        string s = sc.Next();
        int n = s.Length;
        int q = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '?')
            {
                q++;
            }
        }

        long ans = 0;
        for (int i = 0; i < (1 << q); i++)
        {
            char[] t = s.ToCharArray();
            for (int j = 0; j < q; j++)
            {
                if (((i >> j) & 1) == 0)
                {
                    t[GetIndexOfQuestionMark(s, j)] = '0';
                } else
                {
                    t[GetIndexOfQuestionMark(s, 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