bzoj3097 hash killer 1—

题意　　

在 $u64$ 自然溢出下，请输出一串字符串和 $L$，使得对任意 $Base$ 都能找到两个长度为 $L$ 的字串的 $Hash$ 值相同。

分析

$u64$ 自然溢出等价于两个哈希值模 $2^{64}$ 相等。

如果 $Base$ 为偶数，只需构造两串长度至少为65的串且只有最高位不同，因为偶数肯定含有因子2。

如果 $Base$ 为奇数，构造 $i=12$ 的串和其反串。

详细过程推荐博客

#include<bits/stdc++.h>

using namespace std;

char s[( << ) + ];

int  main()

{

    s[] = 'a';

    int n = ;

    for(int i = ;i <;i++)

    {

        for(int j = ;j < n;j++)

        {

            if(s[j] == 'a')  s[j+n] = 'b';

            else s[j+n] = 'a';

        }

        n <<= ;

    }

    int l = n >> ;

    printf("%d %d\n", n +  + l, l);

    printf("%s", s);

    for(int i = ;i < l+;i++)  printf("a");

    printf("\n");

    return ;

}

巴特西

bzoj3097 hash killer 1——构造题

题意

分析

最新文章

热门文章