Hash Killer 两题题解

class Solution_Case
{
	/*
	题解：
	1.https://blog.csdn.net/weixin_45750972/article/details/107457997
	2.oiwiki
	3.https://blog.csdn.net/m0_46209312/article/details/105635114
	结合着看。。。

	首先明白两点：
	1.卡hash的关键在于构造两个不同的串对应的hash值相同。
	2.爆u64相当于对2^64这个数取模。
	如果base是偶数，那么a.........aaa(>64个a)与ba.......aa(a的数量为前面那么串a的数量-1)，这两个串长度相同，hash值相同，显然串是不同的，这样就卡掉了。
	如果base是奇数，就比较麻烦了。

	看vfk的做法吧：
	a \ b表示a能整除b。（orz 具体数学）
	strA . strB代表字符串串联。如"娃" . "哈哈" = "娃哈哈"
	设字符串序列{orzstr[i]}，orzstr[1] = "a", orzstr[i] = orzstr[i - 1] . not(orzstr[i - 1])
	设hash(str)为str的哈希值。

	hash(orzstr[i]) = hash(orzstr[i - 1]) * base ^ |not(orzstr[i - 1])| + hash(not(orzstr[i - 1]))
		= hash(orzstr[i - 1]) * base ^ (2 ^ (i - 2)) + hash(not(orzstr[i - 1]))
		hash(not(orzstr[i - 1])) * base ^ (2 ^ (i - 2)) + hash(orzstr[i - 1])
		hash(orzstr[i]) - hash(not(orzstr[i]))
	= (hash(orzstr[i - 1]) - hash(not(orzstr[i - 1]))) * (base ^ (2 ^ (i - 2)) - 1)

	hash(not(orzstr[i]))似乎是个神奇的东西。
	而我们的目的实际上是要找两个字符串strA, strB使得：hash(strA) % 2^64 = hash(strB) % 2^64
	相当与 2^64 \ hash(strA) - hash(strB)

	设数列{f[i]}，f[i] = hash(orzstr[i]) - hash(not(orzstr[i]))
	f[i] = f[i - 1] * (base ^ (2 ^ (i - 2)) - 1)
	base ^ (2 ^ (i - 1)) - 1
	f[i] = f[i - 1] * g[i - 1]

	问题是不是结束了呢……
	发现没有……
	这样的话我们要使2 ^ 64 \ f[i]，至少得让i = 65……然后发现|orzstr[65]|是个天文数字。

	i > 1时有：
	base ^ (2 ^ (i - 1)) - 1 = (base ^ (2 ^ (i - 2)) - 1) * (base ^ (2 ^ (i - 2)) + 1) = g[i - 1] * 一个偶数
	那么4 \ g[2]，8 \ g[3]...

	所以f[i] 实际上有：
	2 ^ (i * (i - 1) / 2) \ f[i]

	这就是卡base为奇数时的方法。orzstr[12]和not(orzstr[12])即为所求。
	而读入中base既有奇数又有偶数，直接在奇数构造的字符串后面加64个a就可以了。
	*/
};

#include<bits/stdc++.h>
#define N (1<<13)+5
using namespace std;

char s[N];
signed main()
{
	int n = 1;
	s[0] = 'a';
	for (int i = 0; i < 12; i++, n <<= 1)
		for (int j = 0; j < n; j++)
			s[j + n] = s[j] == 'a' ? 'b' : 'a';
	printf("%d %d\n", n + 64, n >> 1);
	printf("%s", s);
	for (int i = 0; i < 64; i++) putchar('a');
	return 0;
}

class Solution_Class
{
	/*
	https://oi-wiki.org/string/hash/#hash-%E5%86%B2%E7%AA%81
	神秘的概率以及神密的泰勒展开，神秘的e
	神密的化简，计算出神秘的概率公式

	exp代表以e为底的指数函数

	*/
};

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;

class Prove
{
  public:
	//我们设 Hash 的取值空间（所有可能出现的字符串的数量）为d
	//计算次数（要计算的字符串数量）为n。
	double Accident_P(int n, int d)
	{
		double A = n*(n - 1), B = -2 * d;
		return 1 - exp(A / B);
	}
	double Log(int A, int x)	//求log  //神笔换底公式
	{
		return log(x) / log(A);
	}
	signed main()
	{
		cout << Log(26, mod) << "\n"; //7
		cout << Accident_P(100000, pow(26, 7)) << "\n";
		return 0;
	}
} sb;

mt19937 Rand(time(NULL)); //默认int类型随机数

int RandNum(int Min, int Max)
{
	int x = Min + Rand() % (Max - Min + 1);
	return x;
}

char getC()
{
	return RandNum('a', 'z');
}

signed main()
{
	//sb.main();
	cout << "100000 7\n";
	for (int i = 1; i <= 100000; i++)
	{
		putchar(getC());
	}
}