[Medium-Hard] UOJ750 【UNR #6】小火车

简要题意

给定一个长度为 $n$ 的序列 $a$ 和一个质数 $p$，保证 $2^n>p$。你需要构造一个长度为 $n$ 的序列 $b$，使得：

• $b_i\in\{-1,0,1\}$，$\exists b_i,b_i\neq 0$。
• $\sum_i a_ib_i\equiv 0\pmod{p}$。

$1\leq n\leq 40$。

思路

去掉 $b_i=0$ 的项，将 $b_i=-1$ 的项移至等号右侧，可以转换题意：

在序列 $a$ 中找到两个不交的非全空子序列 $S,T$，使得 $S,T$ 在模 $p$ 意义下和相等。

随后可以发现，若 $S,T$ 有交，则可以取 $S'=S\setminus(S\cap T),T'=T\setminus (S\cap T)$ 来使得 $S',T'$ 无交，所以可以弱化题意：

在序列 $a$ 中找到两个不同的子序列 $S,T$，使得 $S,T$ 在模 $p$ 意义下和相等。

由于 $n\leq 40$，所以大概率需要一个亚指数时间复杂度的算法，不妨 meet-in-middle，可以求出左半部分的所有子序列的和的可重集合 $S_l$ 和右半部分的 $S_r$。那么需要找到 $a,b\in S_l$ 以及 $c,d\in S_r$ 使得 $a+c\equiv b+d\pmod{p}$。

假如我们确定了 $a+c\equiv K\pmod{p}$，那么可以枚举 $a$，立即确定 $c$，若 $a,c$ 合法，则记录答案。找到了两组这样的答案就足以构造出解了。

现在的问题是如何找到 $K$。不妨二分这个 $K$，我们可以 $O(2^{n/2})$ 的时间复杂度求出有多少个 $a\in S_l,c\in S_r$，使得 $a,c\in [L,R]$。那么可以二分，若区间 $[l,\mathrm{mid}]$ 的答案小于等于 $\mathrm{mid}-l+1$，那么右边一定有答案，否则左边一定有答案。由于 $p<2^n$，根据鸽巢原理，这样是靠谱的。

时间复杂度 $O(n2^{n/2})$。

代码

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using i64 = long long;
const int N = 45, N_ = (1 << 20) + 5;
int n, L, R, lst, rst, answer[N];
i64 m, a[N], ls[N_], rs[N_];
__gnu_pbds::gp_hash_table<i64, pair<int,int>> lsm, rsm;

i64 query(i64 lim){
    int R = rst; i64 ans = 0;
    for(int i=1;i<=lst;i++){
        while(R && ls[i] + rs[R] > lim) R--;
        ans += R;
    }
    return ans;
}

i64 query(i64 L, i64 R){
    return query(R) - query(L - 1) + query(R + m) - query(L + m - 1);
}

bool check(){
    i64 ans1 = 0, ans2 = 0;
    for(int i=1;i<=n;i++){
        if(answer[i] == 1) ans1 += a[i], ans1 %= m;
        else if(answer[i] == -1) ans2 += a[i], ans2 %= m;
    }
    return ans1 == ans2 && !all_of(answer + 1, answer + n + 1, [](int x){return x == 0; });
}

int step;

void record(int A, int B){
    step++, A--, B--;
    if(step > 2) return;
    int tag = (step & 1) ? -1 : 1;
    for(int i=1;i<=L;i++){
        if((A >> (i - 1)) & 1) answer[i] += tag;
    }
    for(int i=L+1;i<=n;i++){
        if((B >> (i - L - 1)) & 1) answer[i] += tag;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m, L = n >> 1, R = n - L;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int S=0;S<1<<L;S++){
        i64 sum = 0;
        for(int i=1;i<=L;i++){
            if((S >> (i - 1)) & 1) sum += a[i], sum %= m;
        }
        ls[++lst] = sum;
        if(!lsm[sum].first) lsm[sum].first = S + 1;
        else if(!lsm[sum].second) lsm[sum].second = S + 1;
    }
    for(int S=0;S<1<<R;S++){
        i64 sum = 0;
        for(int i=L+1;i<=n;i++){
            if((S >> (i - L - 1)) & 1) sum += a[i], sum %= m;
        }
        rs[++rst] = sum;
        if(!rsm[sum].first) rsm[sum].first = S + 1;
        else if(!rsm[sum].second) rsm[sum].second = S + 1;
    }
    sort(ls + 1, ls + lst + 1), sort(rs + 1, rs + rst + 1);
    i64 l = 0, r = m - 1;
    while(l < r){
        i64 mid = (l + r) >> 1;
        if(query(l, mid) > (mid - l + 1)) r = mid;
        else l = mid + 1;
    }
    for(auto it : lsm){
        i64 a = it.first, b = (m + l - a) % m;
        if(lsm[a].first && rsm[b].first) record(lsm[a].first, rsm[b].first);
        if(lsm[a].first && rsm[b].second) record(lsm[a].first, rsm[b].second);
        if(lsm[a].second && rsm[b].first) record(lsm[a].second, rsm[b].first);
        if(lsm[a].second && rsm[b].second) record(lsm[a].second, rsm[b].second);
        if(step >= 2) break;
    }
    assert(check());
    for(int i=1;i<=n;i++) cout << answer[i] << " \n"[i == n];
    return 0;
}

// Written by xiezheyuan