数位的关系
Time Limit : 10000/5000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
对于一个十进制非负整数 $ n $，我们可以按照从高位到低位将其写成一个由数位 $ \texttt 0\sim \texttt 9 $ 构成的字符串 $ S(n) $（不含前导 $ 0 $）。
称一个仅由 $ \texttt < $ 和 $ \texttt > $ 组成的串为关系串。对于一个长度为 $ k $ 的关系串 $ R=r_1r_2\cdots r_k $ 和一个长度为 $ k+1 $ 的字符串 $ S=s_1s_2\cdots s_{k+1} $，如果任意 $ 1\leq i\leq k $，都有关系 $ r_i(s_i,s_{i+1}) $ 成立，则称字符串 $ S $ 满足关系串 $ R $ 的限制。
其中关系 $ r_i(s_i,s_{i+1}) $ 成立只有两种情况，$ r_i=\texttt{<} $ 且 $ s_i < s_{i+1} $ 或者 $ r_i=\texttt{>} $ 且 $ s_i > s_{i+1} $，比较按照字典序顺序。
现在定义 $ f(n,R) $ 表示 $ S(n) $ 中有多少个子序列满足关系串 $ R $ 的限制。给定 $ l,r,R $，求：
$$
\left(\sum_{n=l}^{r}f(n,R)\right) \bmod 998244353
$$
其中一个字符串的子序列定义为从原字符串中删去若干个（可以不删或删空）字符得到的新字符串。
称一个仅由 $ \texttt < $ 和 $ \texttt > $ 组成的串为关系串。对于一个长度为 $ k $ 的关系串 $ R=r_1r_2\cdots r_k $ 和一个长度为 $ k+1 $ 的字符串 $ S=s_1s_2\cdots s_{k+1} $，如果任意 $ 1\leq i\leq k $，都有关系 $ r_i(s_i,s_{i+1}) $ 成立，则称字符串 $ S $ 满足关系串 $ R $ 的限制。
其中关系 $ r_i(s_i,s_{i+1}) $ 成立只有两种情况，$ r_i=\texttt{<} $ 且 $ s_i < s_{i+1} $ 或者 $ r_i=\texttt{>} $ 且 $ s_i > s_{i+1} $，比较按照字典序顺序。
现在定义 $ f(n,R) $ 表示 $ S(n) $ 中有多少个子序列满足关系串 $ R $ 的限制。给定 $ l,r,R $，求：
$$
\left(\sum_{n=l}^{r}f(n,R)\right) \bmod 998244353
$$
其中一个字符串的子序列定义为从原字符串中删去若干个（可以不删或删空）字符得到的新字符串。
Input
本题单个测试点内包含多组测试数据。
第一行一个整数 $ T(1\leq T\leq 10) $，表示数据组数。
对于每组数据，第一行两个整数 $ l,r $ $ (1\leq l\leq r< 10^{500}) $，意义如题。
第二行一个关系串 $ R $ $ (1\leq |R|\leq 500) $，意义如题。
第一行一个整数 $ T(1\leq T\leq 10) $，表示数据组数。
对于每组数据，第一行两个整数 $ l,r $ $ (1\leq l\leq r< 10^{500}) $，意义如题。
第二行一个关系串 $ R $ $ (1\leq |R|\leq 500) $，意义如题。
Output
对于每组数据输出 $ q $ 行，每行一个整数表示答案。
Sample Input
5 12435 12435 << 114514 114514 <>< 1919810 1919810 <><> 1234 4321 <> 114514 1919810 <>>
Sample Output
7 5 5 4628 4377883
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）