fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. public class Test
  5. {
  6.     const long MOD = 1000000007;
  7.  
  8.     abstract class RegNode { }
  9.     class SymbolNode : RegNode
  10.     {
  11.         public char Symbol;
  12.         public SymbolNode(char c) => Symbol = c;
  13.     }
  14.     class ConcatNode : RegNode
  15.     {
  16.         public RegNode Left, Right;
  17.         public ConcatNode(RegNode l, RegNode r) { Left = l; Right = r; }
  18.     }
  19.     class UnionNode : RegNode
  20.     {
  21.         public RegNode Left, Right;
  22.         public UnionNode(RegNode l, RegNode r) { Left = l; Right = r; }
  23.     }
  24.     class StarNode : RegNode
  25.     {
  26.         public RegNode Inner;
  27.         public StarNode(RegNode node) => Inner = node;
  28.     }
  29.  
  30.     class RegexParser
  31.     {
  32.         string s;
  33.         int pos;
  34.  
  35.         public RegNode Parse(string input)
  36.         {
  37.             s = input;
  38.             pos = 0;
  39.             return ParseExpression();
  40.         }
  41.  
  42.         RegNode ParseExpression()
  43.         {
  44.             SkipWhite();
  45.             if (pos >= s.Length) throw new Exception("Błąd w wyrażeniu");
  46.  
  47.             if (s[pos] == 'a' || s[pos] == 'b')
  48.             {
  49.                 var node = new SymbolNode(s[pos]);
  50.                 pos++;
  51.                 SkipWhite();
  52.                 return node;
  53.             }
  54.  
  55.             if (s[pos] == '(')
  56.             {
  57.                 pos++;
  58.                 SkipWhite();
  59.                 var left = ParseExpression();
  60.                 SkipWhite();
  61.  
  62.                 if (pos >= s.Length) throw new Exception("Brak zamknięcia nawiasu");
  63.  
  64.                 if (s[pos] == '*')
  65.                 {
  66.                     pos++;
  67.                     SkipWhite();
  68.                     if (pos >= s.Length || s[pos] != ')')
  69.                         throw new Exception("Brak ) po *");
  70.                     pos++;
  71.                     SkipWhite();
  72.                     return new StarNode(left);
  73.                 }
  74.                 if (s[pos] == '|')
  75.                 {
  76.                     pos++;
  77.                     SkipWhite();
  78.                     var right = ParseExpression();
  79.                     SkipWhite();
  80.                     if (pos >= s.Length || s[pos] != ')')
  81.                         throw new Exception("Brak ) w alternatywie");
  82.                     pos++;
  83.                     SkipWhite();
  84.                     return new UnionNode(left, right);
  85.                 }
  86.                 // (R1R2)
  87.                 var rightConcat = ParseExpression();
  88.                 SkipWhite();
  89.                 if (pos >= s.Length || s[pos] != ')')
  90.                     throw new Exception("Brak ) w konkatenacji");
  91.                 pos++;
  92.                 SkipWhite();
  93.                 return new ConcatNode(left, rightConcat);
  94.             }
  95.             throw new Exception("Niepoprawny symbol w wyrażeniu");
  96.         }
  97.  
  98.         void SkipWhite()
  99.         {
  100.             while (pos < s.Length && char.IsWhiteSpace(s[pos]))
  101.                 pos++;
  102.         }
  103.     }
  104.  
  105.     class NFA
  106.     {
  107.         public List<(char symbol, int to)>[] transitions;
  108.         public List<int>[] epsilons;
  109.         public int Start;
  110.         public int End;
  111.         public int StateCount;
  112.  
  113.         public NFA(int capacity)
  114.         {
  115.             transitions = new List<(char symbol, int to)>[capacity];
  116.             epsilons = new List<int>[capacity];
  117.             for (int i = 0; i < capacity; i++)
  118.             {
  119.                 transitions[i] = new List<(char symbol, int to)>();
  120.                 epsilons[i] = new List<int>();
  121.             }
  122.         }
  123.     }
  124.  
  125.     class NfaBuilder
  126.     {
  127.         int idx = 0;
  128.         public NFA Build(RegNode root)
  129.         {
  130.             int cap = CountNodes(root)*2 + 2;
  131.             var nfa = new NFA(cap);
  132.             var (s, e) = BuildRec(root, nfa);
  133.             nfa.Start = s;
  134.             nfa.End = e;
  135.             nfa.StateCount = idx;
  136.             return nfa;
  137.         }
  138.         (int start, int end) BuildRec(RegNode node, NFA nfa)
  139.         {
  140.             if (node is SymbolNode sym)
  141.             {
  142.                 int s = idx++;
  143.                 int e = idx++;
  144.                 nfa.transitions[s].Add((sym.Symbol, e));
  145.                 return (s, e);
  146.             }
  147.             if (node is ConcatNode c)
  148.             {
  149.                 var left = BuildRec(c.Left, nfa);
  150.                 var right = BuildRec(c.Right, nfa);
  151.                 nfa.epsilons[left.end].Add(right.start);
  152.                 return (left.start, right.end);
  153.             }
  154.             if (node is UnionNode u)
  155.             {
  156.                 int s = idx++;
  157.                 int e = idx++;
  158.                 var left = BuildRec(u.Left, nfa);
  159.                 var right = BuildRec(u.Right, nfa);
  160.                 nfa.epsilons[s].Add(left.start);
  161.                 nfa.epsilons[s].Add(right.start);
  162.                 nfa.epsilons[left.end].Add(e);
  163.                 nfa.epsilons[right.end].Add(e);
  164.                 return (s, e);
  165.             }
  166.             if (node is StarNode st)
  167.             {
  168.                 int s = idx++;
  169.                 int e = idx++;
  170.                 var inner = BuildRec(st.Inner, nfa);
  171.                 nfa.epsilons[s].Add(inner.start);
  172.                 nfa.epsilons[s].Add(e);
  173.                 nfa.epsilons[inner.end].Add(e);
  174.                 nfa.epsilons[inner.end].Add(inner.start);
  175.                 return (s, e);
  176.             }
  177.             throw new Exception("Nieznany typ węzła");
  178.         }
  179.         int CountNodes(RegNode node)
  180.         {
  181.             if (node is SymbolNode) return 1;
  182.             if (node is ConcatNode c) return 1 + CountNodes(c.Left) + CountNodes(c.Right);
  183.             if (node is UnionNode u) return 1 + CountNodes(u.Left) + CountNodes(u.Right);
  184.             if (node is StarNode s)  return 1 + CountNodes(s.Inner);
  185.             return 0;
  186.         }
  187.     }
  188.  
  189.     static List<int>[] EClosureAll(NFA nfa)
  190.     {
  191.         var closures = new List<int>[nfa.StateCount];
  192.         for (int i = 0; i < nfa.StateCount; i++)
  193.             closures[i] = EClosure(i, nfa);
  194.         return closures;
  195.     }
  196.     static List<int> EClosure(int start, NFA nfa)
  197.     {
  198.         var stack = new Stack<int>();
  199.         var visited = new bool[nfa.StateCount];
  200.         var list = new List<int>();
  201.         stack.Push(start);
  202.         visited[start] = true;
  203.         while (stack.Count > 0)
  204.         {
  205.             int s = stack.Pop();
  206.             list.Add(s);
  207.             foreach (int nxt in nfa.epsilons[s])
  208.             {
  209.                 if (!visited[nxt])
  210.                 {
  211.                     visited[nxt] = true;
  212.                     stack.Push(nxt);
  213.                 }
  214.             }
  215.         }
  216.         return list;
  217.     }
  218.  
  219.     static long[] BuildTransitionMatrix(NFA nfa)
  220.     {
  221.         int N = nfa.StateCount;
  222.         var closures = EClosureAll(nfa);
  223.         long[] M = new long[N*N];
  224.         for (int i = 0; i < N; i++)
  225.         {
  226.             foreach (int c in closures[i])
  227.             {
  228.                 foreach (var (symbol, to) in nfa.transitions[c])
  229.                 {
  230.                     foreach (int t in closures[to])
  231.                     {
  232.                         M[i*N + t] = (M[i*N + t] + 1) % MOD;
  233.                     }
  234.                 }
  235.             }
  236.         }
  237.         return M;
  238.     }
  239.  
  240.     static void MatrixMul(long[] A, long[] B, long[] C, int N)
  241.     {
  242.         Array.Clear(C, 0, N*N);
  243.         for (int i = 0; i < N; i++)
  244.         {
  245.             int iN = i*N;
  246.             for (int k = 0; k < N; k++)
  247.             {
  248.                 long val = A[iN + k];
  249.                 if (val == 0) continue;
  250.                 int kN = k*N;
  251.                 for (int j = 0; j < N; j++)
  252.                 {
  253.                     long sum = C[iN + j] + val * B[kN + j];
  254.                     if (sum >= 8000000000000000000L) sum %= MOD;
  255.                     C[iN + j] = sum;
  256.                 }
  257.             }
  258.             // mod po każdej linii
  259.             for (int j = 0; j < N; j++)
  260.                 C[iN + j] %= MOD;
  261.         }
  262.     }
  263.  
  264.     static long[] MatrixPow(long[] M, long exp, int N)
  265.     {
  266.         long[] res = new long[N*N];
  267.         for (int i = 0; i < N; i++) 
  268.             res[i*N + i] = 1;
  269.  
  270.         long[] baseMat = new long[N*N];
  271.         Array.Copy(M, baseMat, N*N);
  272.  
  273.         long[] tmp = new long[N*N];
  274.  
  275.         while (exp > 0)
  276.         {
  277.             if ((exp & 1) == 1)
  278.             {
  279.                 MatrixMul(res, baseMat, tmp, N);
  280.                 // swap
  281.                 var swp = res; 
  282.                 res = tmp; 
  283.                 tmp = swp;
  284.             }
  285.             MatrixMul(baseMat, baseMat, tmp, N);
  286.             {
  287.                 var swp = baseMat;
  288.                 baseMat = tmp;
  289.                 tmp = swp;
  290.             }
  291.             exp >>= 1;
  292.         }
  293.         return res;
  294.     }
  295.  
  296.     static long CountStrings(RegNode root, long L)
  297.     {
  298.         var nfaBuilder = new NfaBuilder();
  299.         var nfa = nfaBuilder.Build(root);
  300.         int N = nfa.StateCount;
  301.         long[] M = BuildTransitionMatrix(nfa);
  302.  
  303.         var Mpow = MatrixPow(M, L, N);
  304.         long result = Mpow[nfa.Start*N + nfa.End] % MOD;
  305.  
  306.         if (L == 0)
  307.         {
  308.             var startClosure = EClosure(nfa.Start, nfa);
  309.             if (startClosure.Contains(nfa.End))
  310.                 result = (result + 1) % MOD;
  311.         }
  312.         return result;
  313.     }
  314.  
  315.     public static void Main()
  316.     {
  317.         // Staram się wczytywać T bezpiecznie
  318.         string tLine = Console.ReadLine();
  319.         if (string.IsNullOrWhiteSpace(tLine))
  320.         {
  321.             // brak danych: np. brak testów
  322.             return; // albo throw
  323.         }
  324.  
  325.         int T = int.Parse(tLine.Trim());
  326.         var parser = new RegexParser();
  327.  
  328.         for (int _t = 0; _t < T; _t++)
  329.         {
  330.             string line = Console.ReadLine();
  331.             // zabezpieczenie przed nullem / pustym wierszem
  332.             if (string.IsNullOrWhiteSpace(line))
  333.             {
  334.                 // Możemy przerwać albo wczytać jeszcze raz itp.
  335.                 // Dla pewności mogę przerwać pętlę testów
  336.                 // break;
  337.                 // lub rzucić nowy wyjątek:
  338.                 throw new Exception("Błąd: pusty wiersz testu!");
  339.             }
  340.  
  341.             line = line.Trim();
  342.             int lastSpace = line.LastIndexOf(' ');
  343.             if (lastSpace == -1)
  344.             {
  345.                 throw new Exception("Brak spacji rozdzielającej wyrażenie i L w wierszu: " + line);
  346.             }
  347.  
  348.             string reg = line.Substring(0, lastSpace).Trim();
  349.             string lStr = line.Substring(lastSpace + 1).Trim();
  350.             if (!long.TryParse(lStr, out long L))
  351.             {
  352.                 throw new Exception("Nieprawidłowa liczba L: " + lStr);
  353.             }
  354.  
  355.             // Parsuję wyrażenie
  356.             var root = parser.Parse(reg);
  357.  
  358.             // Liczę
  359.             long ans = CountStrings(root, L);
  360.             Console.WriteLine(ans % MOD);
  361.         }
  362.     }
  363. }
  364.  
Success #stdin #stdout 0.04s 28496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PGdf2y
problem CTSTRING, based on SPOJ submission 34035854 (NCSHARP), 2025-01-05 14:24:14
language:
C# (NET 6.0)
created:
299 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!