class LCG:
    def __init__(self, seed=1, a=1664525, c=1013904223, m=2**32):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state / self.m

# 使用例
seed = 1320
lcg = LCG(seed=seed)
for _ in range(10):
    print(lcg.next())

state ^= (state << a)
state ^= (state >> b)
state ^= (state << c)

class XorShift32:
    def __init__(self, seed=2463534242):
        self.state = seed

    def next(self):
        x = self.state
        x ^= (x << 13) & 0xFFFFFFFF
        x ^= (x >> 17)
        x ^= (x << 5) & 0xFFFFFFFF
        self.state = x & 0xFFFFFFFF
        return self.state / 0xFFFFFFFF

# 使用例
xorshift = XorShift32(seed=123456789)
for _ in range(5):
    print(xorshift.next())

class MT19937:
    # 初期化（シードによる状態配列の構築）
    def __init__(self, seed):
        self.w, self.n, self.m, self.r = 32, 624, 397, 31
        self.a = 0x9908B0DF
        self.u, self.d = 11, 0xFFFFFFFF
        self.s, self.b = 7, 0x9D2C5680
        self.t, self.c = 15, 0xEFC60000
        self.l = 18
        self.f = 1812433253

        self.MT = [0] * self.n
        self.index = self.n
        self.lower_mask = (1 << self.r) - 1
        self.upper_mask = (~self.lower_mask) & 0xFFFFFFFF

        self.MT[0] = seed
        for i in range(1, self.n):
            self.MT[i] = (self.f * (self.MT[i - 1] ^ (self.MT[i - 1] >> (self.w - 2))) + i) & 0xFFFFFFFF

    # 状態配列の更新（Twist）
    # 複数のビットを結合して新しい状態を作り出す処理
    def twist(self):
        for i in range(self.n):
            x = (self.MT[i] & self.upper_mask) + (self.MT[(i + 1) % self.n] & self.lower_mask)
            xA = x >> 1
            if x % 2 != 0:
                xA ^= self.a
            self.MT[i] = self.MT[(i + self.m) % self.n] ^ xA
        self.index = 0

    # 出力整形（Tempering）
    # 出力する前にビットをシャッフルして統計的性質を良くする
    def extract_number(self):
        if self.index >= self.n:
            self.twist()

        y = self.MT[self.index]
        y ^= (y >> self.u) & self.d
        y ^= (y << self.s) & self.b
        y ^= (y << self.t) & self.c
        y ^= (y >> self.l)
        self.index += 1
        return y & 0xFFFFFFFF

    def random(self):
        return self.extract_number() / 0xFFFFFFFF

# サイコロを2回振るとき 少なくとも1回は1が出る確率
import random

num = 1000000
count = 0
for _ in range(num):
    dices = [random.choice([1,2,3,4,5,6]),random.choice([1,2,3,4,5,6])]
    if 1 in dices:
        count+=1

print(f"少なくとも1が1回はでた回数 : {count}")
print(f"{count * 100 / num}%")

# n人の生徒の中に誕生日が同じ人がいる確率
import random
from collections import Counter

birthdays = list(range(365))
num = 30
cnt, all_cnt = 0,0
for i in range(1000000):
    all_cnt+=1
    tmp = random.choices(birthdays,k=num)
    c = Counter(tmp)
    mx = c.most_common(1)
    if mx[0][1]>1:
        cnt+=1
print(f"誕生日が同じ人がいた回数 : {cnt}")
print(f"誕生日が同じ人がいる確率 : {cnt * 100 /all_cnt}%")

# コインを投げて4回表が出た後の出目の確率
import random

def simulate_coin_tosses(trials):
    result = {'表':0,'裏':0}
    coins = [random.choice(['表', '裏']) for _ in range(trials)]
    for i in range(0, trials-5):
        if coins[i:i+4] == ['表', '表', '表', '表']:
            next = coins[i+4]
            result[next]+=1
    return result['表'], result['裏']

# 試行回数
k = 1000000
total_heads, total_tails = simulate_coin_tosses(k)

print(f"試行回数: {k}")
print(f"表の合計回数: {total_heads}")
print(f"裏の合計回数: {total_tails}")
print(f"4回表が出た後の裏が出る確率は : {total_tails * 100 / (total_heads + total_tails):.6}%")

# コインをnum回投げて、連続して表が出る最高回数
import random

def max_consecutive_heads(trials):
    coins = [random.choice(['表', '裏']) for _ in range(trials)]
    #print(coins)
    #print(f"表の数 : {coins.count('表')}")
    max_count, current_count = 0, 0
    for coin in coins:
        if coin == '表':
            current_count += 1
            max_count = max(max_count, current_count)
        else:
            current_count = 0
    return max_count

# 試行回数
num = 1000
max_heads = [max_consecutive_heads(num) for _ in range(1000)]
mean_heads = sum(max_heads) / len(max_heads)
print(f"試行回数: {num}")
print(f"連続して出現した表の最高回数: {mean_heads}")