Hash Killer 两题题解

· · 个人记录

Hash killer 1

Solve:

神犇思维，构造奇异数据

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;
}

Hash Killer 2

Solve:

神笔证明

随机数卡概率可以过

证明部分log出来的要向上取整

话说取整（7）以后算出来的概率是0.45多，如果不取整的话（6.36）概率为0.993，计算是按不取整算？

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());
    }
}