fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. class Program
  5. {
  6.     private const int MOD = 1000000007;
  7.  
  8.     static void Main(string[] args)
  9.     {
  10.         string inputLine = Console.ReadLine();
  11.         if (string.IsNullOrEmpty(inputLine))
  12.         {
  13.             return; // Jeśli brak danych wejściowych, zakończ program
  14.         }
  15.  
  16.         string[] lines = inputLine.Split(new[] { '\n' }, StringSplitOptions.RemoveEmptyEntries);
  17.         if (!int.TryParse(lines[0], out int t) || t <= 0)
  18.         {
  19.             return;
  20.         }
  21.  
  22.         for (int i = 1; i <= t; i++)
  23.         {
  24.             if (i >= lines.Length)
  25.             {
  26.                 return; // Jeśli brakuje przypadków testowych, zakończ
  27.             }
  28.  
  29.             string line = lines[i];
  30.             string[] input = line.Split();
  31.             if (input.Length != 2 || !int.TryParse(input[1], out int length))
  32.             {
  33.                 return; // Jeśli format testu jest niepoprawny, zakończ
  34.             }
  35.  
  36.             string regex = input[0];
  37.             Console.WriteLine(CountStrings(regex, length));
  38.         }
  39.     }
  40.  
  41.     static int CountStrings(string regex, int length)
  42.     {
  43.         RegexEvaluator evaluator = new RegexEvaluator(regex);
  44.         return evaluator.CountRecognizedStrings(length);
  45.     }
  46.  
  47.     class RegexEvaluator
  48.     {
  49.         private readonly string regex;
  50.         private readonly Dictionary<(string, int), int> memo;
  51.  
  52.         public RegexEvaluator(string regex)
  53.         {
  54.             this.regex = regex;
  55.             this.memo = new Dictionary<(string, int), int>();
  56.         }
  57.  
  58.         public int CountRecognizedStrings(int length)
  59.         {
  60.             return CountStringsHelper(regex, length);
  61.         }
  62.  
  63.         private int CountStringsHelper(string expr, int length)
  64.         {
  65.             if (memo.ContainsKey((expr, length)))
  66.                 return memo[(expr, length)];
  67.  
  68.             if (length == 0)
  69.             {
  70.                 return expr.Contains("*") || expr == "" ? 1 : 0;
  71.             }
  72.  
  73.             if (expr == "a" || expr == "b")
  74.             {
  75.                 return length == 1 ? 1 : 0;
  76.             }
  77.  
  78.             int result = 0;
  79.  
  80.             if (expr.StartsWith("("))
  81.             {
  82.                 int closingIndex = FindClosingParenthesis(expr);
  83.  
  84.                 // Handle star (*) operator
  85.                 if (closingIndex + 1 < expr.Length && expr[closingIndex + 1] == '*')
  86.                 {
  87.                     string inner = expr.Substring(1, closingIndex - 1);
  88.                     result = ComputeStarOperator(inner, length);
  89.                 }
  90.                 // Handle OR (|) operator
  91.                 else if (expr.Substring(1, closingIndex - 1).Contains("|"))
  92.                 {
  93.                     string[] parts = SplitByOperator(expr.Substring(1, closingIndex - 1), '|');
  94.                     foreach (string part in parts)
  95.                     {
  96.                         result = (result + CountStringsHelper(part, length)) % MOD;
  97.                     }
  98.                 }
  99.                 // Handle concatenation
  100.                 else
  101.                 {
  102.                     string left = expr.Substring(1, closingIndex - 1);
  103.                     string right = expr.Substring(closingIndex + 1);
  104.                     for (int i = 0; i <= length; i++)
  105.                     {
  106.                         result = (result + (int)((long)CountStringsHelper(left, i) * CountStringsHelper(right, length - i) % MOD)) % MOD;
  107.                     }
  108.                 }
  109.             }
  110.  
  111.             memo[(expr, length)] = result;
  112.             return result;
  113.         }
  114.  
  115.         private int ComputeStarOperator(string expr, int length)
  116.         {
  117.             long result = 1; // Include the empty string
  118.             long baseCount = CountStringsHelper(expr, 1);
  119.             long multiplier = 1;
  120.  
  121.             for (int i = 1; i <= length; i++)
  122.             {
  123.                 multiplier = (multiplier * baseCount) % MOD;
  124.                 result = (result + multiplier) % MOD;
  125.  
  126.                 if (multiplier == 0) break; // Optimization: Stop if no more valid strings
  127.             }
  128.  
  129.             return (int)result;
  130.         }
  131.  
  132.         private int FindClosingParenthesis(string expr)
  133.         {
  134.             int balance = 0;
  135.             for (int i = 0; i < expr.Length; i++)
  136.             {
  137.                 if (expr[i] == '(') balance++;
  138.                 if (expr[i] == ')') balance--;
  139.                 if (balance == 0) return i;
  140.             }
  141.             throw new ArgumentException($"Invalid expression: unbalanced parentheses at position {expr.Length}");
  142.         }
  143.  
  144.         private string[] SplitByOperator(string expr, char op)
  145.         {
  146.             List<string> parts = new List<string>();
  147.             int balance = 0;
  148.             int start = 0;
  149.  
  150.             for (int i = 0; i < expr.Length; i++)
  151.             {
  152.                 if (expr[i] == '(') balance++;
  153.                 if (expr[i] == ')') balance--;
  154.  
  155.                 if (balance == 0 && expr[i] == op)
  156.                 {
  157.                     parts.Add(expr.Substring(start, i - start));
  158.                     start = i + 1;
  159.                 }
  160.             }
  161.  
  162.             parts.Add(expr.Substring(start));
  163.             return parts.ToArray();
  164.         }
  165.     }
  166. }
  167.  
Success #stdin #stdout 0.05s 28572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rp0EDf
problem CTSTRING, based on SPOJ submission 33960416 (NCSHARP), 2024-12-13 22:30:15
language:
C# (NET 6.0)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!