yukicoder-435

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/435 No.435 占い(Extra)] ==

=== Description ===

{{{
#!html
<p>考虑一个只包含$0$到$9$的数列$S=\{s_1,s_2,...,s_N\}$，进行如下操作
<ol>
<li>假设$S$的长度是$K$，如果$K=1$，结束操作</li>
<li>对于$S$中相邻的两个数$s_i$和$s_{i+1}$ ($1 \le i \le K - 1$)，令它们的和是$s^\prime_{i}$。</li>
<li>如果$s^\prime_{i} \ge 10$，那么用十位和个位的和做替换（例如：$s^\prime_{i}=13$的话，$s^\prime_{i}=1+3=4$）。</li>
<li>把$S$变为$\{s^\prime_1,s^\prime_2,...,s_{K-1}\}$。</li>
<li>重复操作1.</li>
</ol>
</p>

<p>求操作结束后，最后剩下来的那个数的值。</p>

<p>例如$S={3,5,8,2}$的时候，$S$的变化如下：$\{3,5,8,2\} \to \{8, 4, 1\} \to \{3, 5\} \to \{8\}$。</p>

<p>数列$S$可能非常长，会用给定参数$(n,x,a,b,m)$和下面的方法生成：<br>
$r_1=x$<br>
$r_i=((r_{i-1} \text{ XOR } a) + b) \bmod m$ ($2 \le i \le n$)<br>
$S=\{r_1 \bmod 10, r_2 \bmod 10, \dots, r_n \bmod 10\}$
</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$T$<br>
$n_1$ $x_1$ $a_1$ $b_1$ $m_1$<br>
$n_2$ $x_2$ $a_2$ $b_2$ $m_2$<br>
$\vdots$<br>
$n_T$ $x_T$ $a_T$ $b_T$ $m_T$<br>
</p>
<p>$1 \le T \le 10^5, 1 \le n_i, \sum\limits_{i=1}^{T} n_i \le 10^7, 0 \le x_i, a_i, b_i \le 10^9, 1 \le m_i \le 10^9$。</p>
}}}

=== Output ===

对于每组数据，输出最后剩下来的那个数。

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
1
4 3 1 23 39
</pre>
}}}
输出
{{{
#!html
<pre>
8
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
10
1 0 0 0 10
1 1 0 0 10
1 2 0 0 10
1 3 0 0 10
1 4 0 0 10
1 5 0 0 10
1 6 0 0 10
1 7 0 0 10
1 8 0 0 10
1 9 0 0 10
</pre>
}}}
输出
{{{
#!html
<pre>
0
1
2
3
4
5
6
7
8
9
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
10
2 0 0 9 10
2 1 0 7 10
2 2 0 5 10
2 3 0 3 10
2 4 0 1 10
2 5 0 9 10
2 6 0 7 10
2 7 0 5 10
2 8 0 3 10
2 9 0 1 10
</pre>
}}}
输出
{{{
#!html
<pre>
9
9
9
9
9
9
9
9
9
9
</pre>
}}}

==== Sample 4 ====
输入
{{{
#!html
<pre>
10
10 261841953 671191155 663795355 305410838
10 862899986 184211912 62933042 787920138
10 753226285 21356280 298276938 21255922
10 958211219 805249349 595459506 854076698
10 410276862 213541814 550850232 377093341
10 357163853 623258597 838281966 723982380
10 614756466 807929090 709298917 299243176
10 523897658 967067335 799279896 655953200
10 626854805 479600382 724964117 820523234
10 287024904 121730613 972092257 520943977
</pre>
}}}
输出
{{{
#!html
<pre>
1
3
3
9
7
8
9
2
1
9
</pre>
}}}

No.435 占い(Extra)

Description

考虑一个只包含$0$到$9$的数列$S=\{s_1,s_2,...,s_N\}$，进行如下操作

  1. 假设$S$的长度是$K$，如果$K=1$，结束操作
  2. 对于$S$中相邻的两个数$s_i$和$s_{i+1}$ ($1 \le i \le K - 1$)，令它们的和是$s^\prime_{i}$。
  3. 如果$s^\prime_{i} \ge 10$，那么用十位和个位的和做替换（例如：$s^\prime_{i}=13$的话，$s^\prime_{i}=1+3=4$）。
  4. 把$S$变为$\{s^\prime_1,s^\prime_2,...,s_{K-1}\}$。
  5. 重复操作1.

求操作结束后，最后剩下来的那个数的值。

例如$S={3,5,8,2}$的时候，$S$的变化如下：$\{3,5,8,2\} \to \{8, 4, 1\} \to \{3, 5\} \to \{8\}$。

数列$S$可能非常长，会用给定参数$(n,x,a,b,m)$和下面的方法生成：
$r_1=x$
$r_i=((r_{i-1} \text{ XOR } a) + b) \bmod m$ ($2 \le i \le n$)
$S=\{r_1 \bmod 10, r_2 \bmod 10, \dots, r_n \bmod 10\}$

Input

$T$
$n_1$ $x_1$ $a_1$ $b_1$ $m_1$
$n_2$ $x_2$ $a_2$ $b_2$ $m_2$
$\vdots$
$n_T$ $x_T$ $a_T$ $b_T$ $m_T$

$1 \le T \le 10^5, 1 \le n_i, \sum\limits_{i=1}^{T} n_i \le 10^7, 0 \le x_i, a_i, b_i \le 10^9, 1 \le m_i \le 10^9$。

Output

对于每组数据，输出最后剩下来的那个数。

Sample

Sample 1

输入

14 3 1 23 39

输出

8
Sample 2

输入

101 0 0 0 101 1 0 0 101 2 0 0 101 3 0 0 101 4 0 0 101 5 0 0 101 6 0 0 101 7 0 0 101 8 0 0 101 9 0 0 10

输出

0123456789
Sample 3

输入

102 0 0 9 102 1 0 7 102 2 0 5 102 3 0 3 102 4 0 1 102 5 0 9 102 6 0 7 102 7 0 5 102 8 0 3 102 9 0 1 10

输出

9999999999
Sample 4

输入

1010 261841953 671191155 663795355 30541083810 862899986 184211912 62933042 78792013810 753226285 21356280 298276938 2125592210 958211219 805249349 595459506 85407669810 410276862 213541814 550850232 37709334110 357163853 623258597 838281966 72398238010 614756466 807929090 709298917 29924317610 523897658 967067335 799279896 65595320010 626854805 479600382 724964117 82052323410 287024904 121730613 972092257 520943977

输出

1339789219