No.1004 サイコロの実装 (2)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 146
作問者 : trineutrontrineutron / テスター : 37zigen37zigen
8 ProblemId : 3862 / 出題時の順位表
問題文最終更新日: 2020-03-06 21:01:44

問題文

線形合同法という擬似乱数生成法がある。正の整数$a, b, m$を用いて$x_{i+1}=ax_i+b \pmod{m}$という漸化式で乱数を生成する。例えば、$a=3, b=1, m=7, x_0=0$のとき$x_1=1, x_2=4, x_3=6, x_4=5, x_5=2, x_6=0, x_7=1, \dots$となる。

剰余を求める演算は通常は遅いが、$m=2^{32}$のとき、32bit符号なし整数型で$ax_i+b$を計算するとオーバーフローにより剰余が計算できるため高速に計算できる。このとき、$a$を$4$で割った余りが$1$となる整数、$b$を奇数にすると最大周期$2^{32}$になることが知られている。以下、$m=2^{32}$とする。

サイコロを実装するためには$1$から$6$までの整数がおおむね等確率で出る乱数が必要なので、$x_i$を$6$で割った余りに$1$を足した整数をサイコロの出目とする。

高橋君と青木君はこのサイコロを使って以下のようなすごろくをすることにした。

2人とも最初はマス$0$にいる。高橋君を先手として交互にサイコロを振り、出目の分だけ進む。止まったマス目が奇数なら黒石を、偶数なら白石を得る。これを$N$回繰り返し、黒石と白石の組1つにつき$1$点が得られる。

例えば、$N$が$3$、出目が$1, 3, 2, 6, 4, 5$のとき、高橋君はマス$1, 3, 7$に止まり黒石$3$個を得て、青木君はマス$3, 9, 14$に止まり黒石$2$個と白石$1$個を得る。得点はそれぞれ$0$点と$1$点となる。

$a, b, x_0, N$が与えられるので、高橋君と青木君のそれぞれの得点を求めよ。なお、サイコロの最初の出目は$x_1$を$6$で割った余りに$1$を足した整数とする。

入力

$a\ b\ x_0\ N$

入力は全て整数
$0 \le a, b, x_0, N \lt 2^{32}$
$a$を$4$で割った余りは$1$
$b$は奇数

出力

高橋君と青木君の得点をスペース区切りで出力してください。最後に改行してください。

サンプル

サンプル1
入力
5 1 1 1
出力
0 0

$x_1 = 6, x_2 = 31$なので、高橋君は$1$を出してマス$1$に止まり、黒石を得ます。次に、青木君が$2$を出してマス$2$に止まり、白石を得ます。2人とも黒石と白石の組はないので、得点は$0$です。

サンプル2
入力
3000000001 3000000001 3000000001 0
出力
0 0

サイコロを振らない場合もあります。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。