题目背景

“同志，你只是一直在回答‘不可以’吗？你到底有没有好好判断形势？现在是关乎国家危亡的时刻……”

“总司令，您知道我不太聪明，没找到快速而正确地计算出结果的办法，但是据某项统计，我一直回答 NO 的话，在一次战役中判断完全正确的概率是 $45\%$。”

在极端的决策压力下，看似荒唐的随机决策有时是唯一的选择。作为指挥部的总司令，你需要通过模拟实验来验证：如果决策者以 $50\%$ 的概率随机输出，在特定的非线性判定机制下，胜率究竟几何？

题目描述

1. 获取指示函数：

bool get_instruction(unsigned long long seed) {
    unsigned long long x = seed ^ 0x5DEECE66DL;
    x = (x * 0x27BB2EE687B0B0FDL + 0xBL);
    x = (x ^ (x >> 31)) ^ (x << 13);
    int count = 0;
    unsigned long long v = (x < 0) ? -x : x;
    while (v > 0) {
        v &= (v - 1);
        count++;
    }
    return (count % 2 == 0);
}

2. 种子更新函数：

unsigned long long next_seed(unsigned long long seed, bool decision) {
    unsigned long long x = seed;
    x ^= (x << 21);
    x ^= (x >> 35);
    x ^= (x << 4);
    unsigned long long magic = decision ? 0x3141592653589793L : 0x2718281828459045L;
    return (x + magic) * 6364136223846793005L + 1L;
}

模拟规则：

• 初始给定一个 seed 和轮数 n。
• 在每一轮中，总司令有 $50\%$ 的概率选择 Yes（true），$50\%$ 的概率选择 No（false）。
• 每一轮，首先根据当前 seed 调用 get_instruction 得到“正确指示”。
• 然后根据总司令的决策 decision 和当前 seed 调用 next_seed 产生下一轮的种子。
• 一次战役包含 $n$ 轮决策。当总司令决策与指示完全一致的次数大于等于 $n/2$ 时，判定为战役胜利。

请计算总司令胜出的概率。

输入格式

输入两个整数 $seed$ 和 $n$，其中 $0 \le seed \le 2 ^ {63} - 1$，$1 \le n \le 24$。

输出格式

输出胜率，格式为 XX.XX%（结果需向下取整保留两位小数）。

样例

123456 2

75.00%

样例解释

初始 $seed = 123456$，$n = 2$。胜利条件为：正确次数 $\geq 2/2 = 1$。

1. 第一轮：get_instruction(123456) 返回 false (No)。

• 分支 A (决策 No)：正确。seed 更新为 next_seed(123456, false) = 6904170720195229645。
• 分支 B (决策 Yes)：错误。seed 更新为 next_seed(123456, true) = 3416414079416382083。

2. 第二轮：

• 由分支 A 继续：get_instruction(6904170720195229645) 返回 false (No)。

  • 无论选什么，正确次数最多为 1，均胜。

• 由分支 B 继续：get_instruction(3416414079416382083) 返回 false (No)。

  • 若选 No，正确次数为 1，胜。
  • 若选 Yes，正确次数为 0，败。