2021牛客暑期多校训练营1 H

H. Hash Function

题目描述

For a given set , we called a hash function perfect hash function of , if it satisfies , .

Given a set S with non-negative integers, please find the minimum positive integer seed that function ​ is a perfect hash function of ​.

输入描述

The first line of input contains one integer , describing the size of set .

The second line contains () integers , describing the elements in .

It is guaranteed that , .

输出描述

Output one integer in a line, indicating the answer.

示例1

输入

3
2 3 4

输出

3

示例2

输入

3
1 2 4

输出

4

示例3

输入

10
0 7 23 18 29 27 6 28 24 11

输出

15

思路

  ​，​；等价于 ​，​。注意到数据范围较小，集合中任意两数的差属于 ​​，可进行多项式优化，用 NTT 或 FTT 得到某个差值是否存在。

  定义两个多项式 ​​​，系数分别为 ​​​；两者的卷积为 ​​​，​​​。我们的想法是令 ​​​ 为差值 ​​​ 是否存在的标志，那么卷积 ​​​ 的限制条件应该为 ​​​，但是下标不可能为负数，因此我们需要将 ​​​ 的系数下标增加一个偏移量 ​​​。若 ​​​，则 ​​​，​。两个多项式进行卷积运算，就能得到差值是否存在的信息，；若 ，就代表 的差值存在。

  我们枚举最终的答案 ​​​​，根据抽屉原理，​​​​ 可以直接从 ​​​​ 开始枚举。对于当前的模数 ​​​​​，我们需要快速查询存在的差值中是否有一个差值 ；我们只需要枚举 的所有倍数，检查是否存在 的某个倍数正好是 ​​​​​ 中两数的差。枚举的时间复杂度是 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2021牛客多校训练营1 H
Date: 2021 July 24th
Description: NTT, Number Theory
*******************************************************************/
#include<iostream>
using namespace std;
typedef long long ll;
const int SIZE = 1 << 21;
const int MAX = 500000;
const int MOD = 998244353;
int n;
ll a[SIZE], b[SIZE], res[SIZE], rev[SIZE];
int len = 1 << 20;
ll quickPow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % MOD;
        }
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}
void NTT(ll* a, short opt)
{
    for (int i = 0; i < len; i++)
    {
        if (i < rev[i])
        {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int k = 2; k <= len; k <<= 1)
    {
        ll m = k >> 1, x = quickPow(3, (MOD - 1) / k), w = 1, v;
        if (opt == -1)
        {
            x = quickPow(x, MOD - 2);
        }
        for (int i = 0; i < len; i += k, w = 1)
        {
            for (int j = i; j < i + m; j++)
            {
                v = w * a[j + m] % MOD;
                a[j + m] = (a[j] - v + MOD) % MOD;
                a[j] = (a[j] + v) % MOD;
                w = w * x % MOD;
            }
        }
    }
    if (opt == -1)
    {
        ll inv = quickPow(len, MOD - 2);
        for (int i = 0; i < len; i++)
        {
            a[i] = a[i] * inv % MOD;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        a[x] = 1;
        b[MAX - x] = 1;
    }
    for (int i = 0; i < len; i++)
    {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
    }
    NTT(a, 1);
    NTT(b, 1);
    for (int i = 0; i < len; i++)
    {
        res[i] = a[i] * b[i] % MOD;
    }
    NTT(res, -1);
    // 所有差是否存在都已经知道
    for (int ans = n;; ++ans)
    {
        bool ok = true;
        for (int p = ans; p <= MAX; p += ans)
        {
            if (res[p + MAX])
            {
                ok = false;
                break;
            }

        }
        // 没必要枚举负数差值，因为两数的两个差互为相反数。
        // for (int p = -ans; p >= -MAX; p -= ans)
        // {
        //     if (res[p + MAX])
        //     {
        //         ok = false;
        //         break;
        //     }
        // }
        if (ok)
        {
            cout << ans << endl;
            return 0;
        }
    }
}