#YDRG004C. 不妨学一学《深入理解计算机系统》

不妨学一学《深入理解计算机系统》

题目背景

小芙和小希某天刚考完 CSAPP(深入理解计算机系统)这门课的期末,便凑在一次开始对答案。我们都知道,考完试忙着对答案往往会有“惊喜”降临。不出所料,他们发现了这样一个惊喜——

题目描述

他们依稀记得,考场上有一道题是这样的:

给定两个长度均为 kk 的二进制串,请你计算两者相乘的结果,且将结果保留为 2k2k 位。

但是,他们忘记这两个二进制串是在做有符号二进制数乘法,还是无符号二进制数乘法了。

小芙是按有符号乘法做的,而小希是按照无符号乘法做的——这两者显然有着天壤之别。以下是一些简单介绍:

有符号数的二进制表示是该数的补码,最高位默认是符号位

举个例子来讲,1110100111010101无符号乘法时,分别表示 233233211211233×211233 \times 211 答案为 1100 0001 1101 1101(2)=49629(10)

而在有符号乘法时,两者分别表示 23-2343-4323×(43)-23\times (-43) 答案为 0000 0011 1101 1101(2)=989(10)

在发现这一事实后,悲观的小芙认为:

“完了,这下咱俩至少一个要完蛋了!”

而乐观的小希则觉得:

“不一定,万一两个答案有重合的地方呢?”

到最后,两人争执不下,两人只能打了一个赌:

我们默认两个人算的答案在各自的算法下都是计算正确的。设两人答案(答案指的是长度为 2k2k 的结果二进制串)里相同的位数为 pp,不同的位数为 qq 。显然 p+q=2kp+q=2k。那么:

  • pqp\geq q 时,小芙要请小希吃饭。
  • p<qp<q 时,小希要请小芙吃饭。

现在,给定你两个长度均为 kk0101 串,请你计算出谁要请吃饭。

注意,我们认为结果一定是 2k2k 位,这可能需要补足额外的前导 0 。

输入格式

由于输入量过大,为了防止输入导致的额外耗时,采取种子生成的方式生成输入数据。

11 行共一个整数 tt,表示单个测试点的数据组数。

2t+12\sim t+1 行,每行包含 44 个种子 k,a,b,c,dk,a,b,c, d。其中 kk 为 01 串的长度,详情请见题目描述。a,b,c,da,b,c, d 为生成参数。设 int 类型数组 sA[], sB[] 分别表示需要做乘法两个 01 串,则具体的生成逻辑如下:

const int N = 3000010 ;

int k, a, b, c, d ;
int sA[N], sB[N] ; 

int main(){
	cin >> k >> a >> b >> c >> d ;
	for (int i = 1 ; i <= k ; ++ i)
		sA[i] = ((1ll * sA[i - 1] * a + b) % c) ^ d ;
	for (int i = 1 ; i <= k ; ++ i)
		sB[i] = ((1ll * sB[i - 1] * d + c) % b) ^ a ;
	for (int i = 1 ; i <= k ; ++ i){
		sA[i] &= 1 ; 
		sB[i] &= 1 ;
	}
    
    return 0 ;
}

输出格式

输出共 tt 行。对于每一组询问,设小芙、小希两人答案里相同的位数为 pp,不同的位数为 qq 。显然 p+q=2kp+q=2k。那么:

  • pqp\geq q 时,小芙要请小希吃饭,此时输出一行共一个字符串 Frieren
  • p<qp<q 时,小希要请小芙吃饭,此时输出一行共一个字符串 Himmel

样例 #1

输入样例

1
4 12 15 17 8

输出样例

Frieren

样例 #1 解释

当输入为 4 12 15 17 8 时,两个字符串分别为 10000100。当将二者视为有符号数时,两者分别代表十进制下的 8-844,相乘得到 -32(10)=00100000(2)。当将二者视为无符号时,两者分别代表十进制下的 8844,相乘得到 32(10)=00100000(2)

因此,相同的位数 p=8p=8,不同的位数 q=0q=0pqp\geq q,小芙要请小希吃饭,因此输出一行一个字符串 Frieren

样例 #2

输入样例

1
4098 13354 2016 17789 3213

输出样例

Frieren

数据范围

对于 10%10\% 的数据,k=a=b=c=d=1k=a=b=c=d=1

对于 30%30\% 的数据,k6000k\leq 6000

对于 50%50\% 的数据,k3×104k\leq 3\times 10^4

对于 70%70\% 的数据,k2×105k\leq 2\times 10^5

对于全部 100%100\% 的数据,$k\leq 3\times 10^6,0< a,b,c,d\le 2\times 10^9,t\leq 5$。