P9512题解

EXODUS · 2023-08-10 22:54:56 · 题解

Part 1：前言

大概是这三年以来做过的最好的题？

Part 2：正文

下文中令 n=N,s=S。

首先我们考虑一个限制为 M=1002 的做法，对于一个长度为 n 的字符串，我们考虑设计一个算法去按位定位每一位的答案。假设当前我们要确定第 i 位的值，那么考虑构造一种序列，使得前 i-1 位不会影响答案且最后答案只与第 i 位的值有关。也就是说，在到达 i 后，答案始终固定。而对于一个位置 i，简单构造可知若 i=a_i=b_i，则到达此位置后的结果不影响答案。因此不难想到构造序列 a=[1,2,\cdots,i-1,i,i,i+1],b=[1,2,\cdots,i-1,i+1,i,i+1]。期望得分 10 分。

现在我们进军 M=502。考虑上面的做法实质上能够让我们在 M=L+3 的长度限制之内确定一段前缀的答案，那么我们现在自然想到能不能也在 O(L) 的限制内确定一段后缀，那么我们知道所有 j\in[i+1,n] 后缀的 s_j 的值，要推出来 s_i 的值，这相当于判定一段后缀是否和某个给定串 t 相等。具体而言，我们试图构造两个数列，若当前机器中的字符为 i，则意味着当前的后 i 位和 t 的前 i 位相同，这个可以暴力构造，但对于不同的字符串有不同的形式，故具体实现和构造方式可以参考代码。

这个做法似乎没啥前途，我们不妨跳出这个来想一想。题目的要求实际上是要我们求 n 个 0/1 变量的值，而求未知变量的值我们能够想到的一个做法是构造若干线性无关的方程。而我们还知道存在一组合法解使得 x_i\in\{0,1\}，因此我们可以考虑模 2 意义下的方程组。考虑每次询问出下标 i 满足 i\equiv q\pmod p 且 s_i=1 的 i 的个数模 2 后的值。通过手玩发现可以构造两个长度为 p 的环，能改变所在的环的位置只有在环上的第 q 个位置且此时走到的 s_i 为 1，实际的构造可以参考代码。

打表发现通过这个方法获得 1000 个独立方程组的 p 的最小值是 57，故此时有 M=114，求出方程组后高斯消元或其它做法即可。

其实到了这一步以后正解自然的已经出来了。结合前两种做法我们可以把序列长度缩短到 799，也就是说我们此时只需要求出 799 个独立的方程组，此时 p 的最小值为 51，恰好顶着上界。

于是做完了。

Part 3：代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define Debug(...) fprintf(stderr,__VA_ARGS__)
const int N=1e3+7,M=1e2+2,L=1e2+7;
typedef long long ll;
typedef vector<int> vi;
typedef bitset<N> bit;

int n,m;
vi a,b;
string str;

int Query(int m, std::vector<int> a, std::vector<int> b);

struct Basis{
    vector<pair<int,bit>>S;
    bool ins(bit cur){
        for(auto &[ft,bt]:S)if(cur.test(ft))cur^=bt;
        if(cur.any())return S.eb(cur._Find_first(),cur),1;
        else return 0;
    }
    int size(){
        return S.size();
    }
};

vector<tuple<int,int,bit>>buc[L],qmd;
vector<pair<int,bit>>qft,qbk;

vector<bit>mar;

string Solve(int _n){
    n=_n;
    auto getmd=[&](){
        bit sit;
        rep(x,1,M>>1)rep(r,0,x-1){
            rep(i,0,n-1)sit.set(i,i%x==r);
            buc[2*x].eb(x,r,sit);
        }
    };
    auto getft=[&](){
        bit sit;
        rep(i,0,M-3){
            rep(j,0,n-1)sit.set(j,j==i);
            buc[i+3].eb(-1,i,sit);
        }
    };
    auto getbk=[&](){
        bit sit;
        rep(i,0,M-2){
            rep(j,0,n-1)sit.set(j,j==(n-1-i));
            buc[i+2].eb(-2,i,sit);
        }
    };
    auto merge=[&](){
        Basis tmp;
        rep(i,1,M)for(auto &[x,r,s]:buc[i]){
            if(tmp.size()==n)break;
            if(tmp.ins(s)){
                // Debug("%d %d ",x,r);
                // for(int j=0;j<n;j++)Debug("%d",s.test(j));
                // Debug("\n");
                if(x==-1)qft.eb(r,s);
                else if(x==-2)qbk.eb(r,s);
                else qmd.eb(x,r,s);
            }
        }
    };
    getft(),getmd(),getbk(),merge();

    auto qryft=[&](){
        auto loop=[&](int i){a[i]=i,b[i]=i;};
        for(auto &[p,s]:qft){
            m=p+3;
            a.resize(m),b.resize(m);
            rep(j,0,p-1)a[j]=b[j]=j+1;
            a[p]=p+1,b[p]=p+2;loop(p+1),loop(p+2);
            auto cur=s;cur.set(n,Query(m,a,b)==p+2);
            mar.eb(cur);
        }
    };
    auto qrybk=[&](){
        vi res;
        for(auto &[p,s]:qbk){
            res.insert(res.begin(),0);
            m=p+2;a.resize(m),b.resize(m);
            auto get=[&](int v,int _p,int i){
                auto cur=vi(res.begin(),res.begin()+i);
                cur.push_back(v);
                per(j,min(_p+1,i+1),1)
                    if(vi(cur.end()-j,cur.end())==vi(res.begin(),res.begin()+j))
                        return j;
                return 0;
            };
            rep(i,0,p+1)a[i]=get(0,p,i),b[i]=get(1,p,i);
            auto cur=s;cur.set(n,(res[0]=(Query(m,a,b)!=p+1)));
            mar.eb(cur);
        }
    };
    auto qrymd=[&](){
        for(auto &[x,r,s]:qmd){
            m=2*x;a.resize(m),b.resize(m);
            rep(j,0,x-1)a[j]=b[j]=(j+1)%x,a[j+x]=b[j+x]=(j+1)%x+x;
            swap(b[r],b[r+x]);
            auto cur=s;cur.set(n,Query(m,a,b)>=x);
            mar.eb(cur);
        }
    };
    auto solve=[&](){
        rep(i,0,n-1){
            int k=-1;
            rep(j,i,n-1)if(mar[j].test(i)){k=j;break;}
            // Debug("%d\n",k);
            swap(mar[i],mar[k]);
            rep(j,0,n-1)if(j!=i&&mar[j].test(i))mar[j]^=mar[i];
        }
        str.resize(n);
        rep(i,0,n-1)str[i]=mar[i].test(n)+'0';
        // Debug("%s\n",str.c_str());
    };

    qryft(),qrymd(),qrybk();solve();
    // for(auto bt:mar){for(int j=0;j<n;j++)Debug("%d",bt.test(j));Debug(" %d\n",bt.test(n));}

    return str;
}

Part 4：后文

引用一下 vfk 大爷的话。

一道好题不应该是两道题拼在一起，一道好题会有自己的idea —— 而它应该不加过多包装地突出这个idea。

一道好题应该新颖。真正的好题，应该是能让人脑洞出新的好题的好题。

一道好题应该具有它的选拔性质，具有足够的区分度。应该至少4档部分分，让新手可以拿到分，让高手能够展示自己的实力。

这道题最让人拍案叫绝的是自然是转为求解线性方程组的一步，而以长度相关的代价询问后缀又给了这道题恰到好处的区分度。就这两点而言，无论是从比赛还是练习的角度，这道题也许都称得上是一道好题。