题解 P8568 [JRKSJ R6] func

vectorwyx · 2022-10-13 20:24:43 · 题解

好题，yzy 神中神 orz。

先来考虑 Sub2，也就是已知 p,k\bmod p,2b\bmod p 怎么做。为方便行文以下如无特殊说明提到 k,b 均默认为模 p 意义下。一个自然的思路是二分，每次询问 g(1)+g(x)，如果 [1,x) 中没有拐点答案应为 (x+1)k+2b，否则为 xk+2b。在已知 k,2b 且 k\not= 0 时可以据此判断出拐点所在位置，询问次数为 \log_2n=30。

接下来考虑 Sub3，也就是赛时的正解。Sub3 在 P 改为 50 的同时多了 12 次询问，由前文不难想到我们应当用多出来的这 12 次询问确定一个合适的 p，满足 k\bmod p\not= 0，在确定 p 的同时还需要确定 k,2b 的取值。

先解决第一个问题，对于某个 p 如何判断 k 在模 p 意义下是否为 0。首先一次询问就确定不现实，因为这里有 k,b 两个变量。两次的话只需要任选三个数 x<y<z 满足 y+1<z 然后询问 g(x)+g(y) 与 g(x)+g(z)，将询问结果作差得到 a=g(z)-g(y)=(z-y)k 或 (z-y-1)k，由于 y+1<z，a=0 当且仅当 k=0。即 k\bmod p=0\iff g(x)+g(y)=g(x)+g(z)。

第二个问题是在找到一个合法的 p 后如何求出 k,2b。考虑能否利用检验 k\bmod p\not= 0 时得到的 g(x)+g(y) 与 g(x)+g(z) 来解出 k,2b。这看上去是一个模意义下的二元一次方程，可惜由于拐点的存在，未知元 k 的系数是不确定的。好在当 x+1=y,z+1=x 时我们能够根据交互库是否返回 -1 来排除拐点的影响，即询问 s=g(x-1)+g(x) 与 t=g(x)+g(x+1)，如果两者中有任意一个返回了 -1 可以直接确定拐点，否则两个方程是确定的：

不妨令 x=2，则有：

这里需要用到 2 的逆元，如果 2|p 那么 k,2b 就又不确定了，因此 p 的取值只能为奇数。现在需要从 [1,50] 中选 12/2=6 个奇数出来，满足它们中至少有一个能整除斜率 k，显然这 6 个数的 \operatorname{lcm} 越大越容易成功，问题变为选出 \operatorname{lcm} 最大的 6 个奇数。可以写个 dfs 搜，也可以直接手动构造，思路是贪心，从大到小选，每次选一个对当前 \operatorname{lcm} 贡献最大的数丢进集合里，这个贪心在范围大的时候不对，但是范围小的时候能凑合着用。按这个思路选出来的数是 49,47,45,43,41,37，其 \operatorname{lcm} 为 6760214685，设为 B。那么它够不够用呢？由于题目只给了 g(x) 的上界，所以我们还需要分析一下斜率 k 的上界。令 g(x) 的上界为 A，则：

令 b'=-b，由 -b\le \dfrac{A-b}{n} 得 nb'\le A+b'\iff b'\le\dfrac{A}{n-1}。那么 k\le\dfrac{A+b'}{n}\le \dfrac{A+\frac{A}{n-1}}{n}=\dfrac{A}{n-1}。对于 Sub5，将 n=1162261531,A=7857125847061472735 代入得 A\le6760204690<B=6760214685，刚刚好。对于 Sub3,4，将 n=10^9,A=10^{18} 代入显然也是符合要求的。但是有个小问题是 Sub3,4 中的 n 有可能比 10^9 小，它带来的影响是抬高了 k 的上界，此时可能会用到多于 6 个奇数，多一个奇数会使所需询问次数多 2，这意味着 k 的上界 \dfrac{A}{n-1}\ge B\iff n\le \left\lfloor\dfrac{A}{B}\right\rfloor+1=147924297，也就说如果想要把上界抬高到 6 个奇数无法搞定 n 至少要降至 147924297< \dfrac{10^9}{4}，即二分次数至少会减 2，因此即使 n<10^9 也不会出事。多两个奇数或更多也是类似的分析。至此我们解决了赛时的限制。

赛后毒瘤 yzy 把次数卡到了 32 次。原本的做法由两部分组成：第一部分是根据事先定好的模数集合用 12 次询问确定合适的模数 p，这过程中除了 k,2b 的取值外不会获得任何有效信息，不过这已经很强了，因为它实际上给出了修改前的函数具体长啥样。第二部分是根据已知信息确定拐点位置，我们需要把这部分的次数卡到 20。回想最开始在 Sub2 中提到的二分做法，每次询问 g(1)+g(x)，然后把它与修改前 g(1)+g(x) 应该是什么做对比，以此推出拐点对于 x 的影响，进而得到拐点与 x 的相对位置。这里固定的 1 看起来很奇怪，因为 1 始终不会受到拐点影响，那么感觉上讲根据 g(1)+g(x) 能得到的信息不如询问 g(x)+g(y)。由于拐点会偏移一段后缀，因此 g(x)+g(y) 的偏移量有三种可能：0,k,2k，分别对应拐点位于 [y,r),[x,y),[l,x)，其中 [l,r) 为当前拐点所在的位置范围。所以把二分改为三等分当前区间，次数由 \log_2 n 变为 \log_3n，刚好能通过 Sub5！

对于 Sub4 会遇到与之前同样的问题，也就是若 n 减小导致 k 的上界抬高对询问次数的影响。仍然套用前文的分析，然而 147924297>\dfrac{10^9}{9}，看起来有点寄，毕竟在上界抬高到 6760214685 时 \log_3 n 只减小了 1，而确定模数时用的询问次数增加了 2。幸运的是 \lfloor\log_3{10^9}\rfloor=18，换句话说它有 2 次的冗余量，因此不会炸。而之后模数集合的大小不会增加太多，粗略地估计一下，大小每增加 1 其 \operatorname{lcm} B 就会翻至少 20 倍。n\le \left\lfloor\dfrac{A}{B}\right\rfloor+1，所以 n 的上界也会减少 20 倍，对应 \log_3 n 会减小 2，能够抵消模数集合大小增加 1 对询问次数的影响。

实现时还有个细节是如何尽量三等分区间 [l,r)，设三等分点分别为 x<y，则 x-l=y-x=r-y，解得 x=\dfrac{2l+r}{3},y=\dfrac{l+2r}{3}。

代码如下（码 \LaTeX 不易，能不能点个赞再走啊 awa）：

//author:望远星
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define emp emplace
#define re return
//#define int ll 
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){int ch=getchar(),x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

namespace func{
int k=100,b=11111,t=7;
ll F(int x){
    if(t<x) return k*(x-1ll)+b;
    return (ll)k*x+b;
}
//using func::F;
int cnt;

inline int ask(int l,int r,int p){
    printf("? %d %d %d\n",l,r,p);
    cnt++;
    cout.flush();
    return read();
    //printf("%d\n",(F(l)+F(r))%p);
    //if(F(l)==F(r)) return -1;
    //return (F(l)+F(r))%p;
}

void answer(int x){
    printf("! %d\n",x);
    cout.flush();
    if(!read()) exit(0);
    //if(t!=func::t) exit(0);
//    cout<<"cnt="<<cnt<<'\n';    
}
}
using func::answer;
using func::ask;

const int P[]={49,47,45,43,41,37,31,29,25,23};
const int ni[]={25,24,23,22,21,19,16,15,13,12};
int n;

void solve(){
    int L=1,R=read(),q=read(),pp=read();
    if(pp==2){
        int l=1,r=R,mid;
        while(l<=r){
            //printf("[%d,%d]\n",l,r);
            if(r-l<=1){
                answer(l);
                return;
            }
            mid=l+((r-l)>>1);
            //printf("mid=%d\n",mid);
            int x=ask(1,mid,2);
            if(x==-1){
                answer(1);
                return;
            }
            if((mid&1)^(x&1)) l=mid;
            else r=mid;
        }
        re;
    }
    int p=0,k=0,b=0;
    fo(i,0,9){
        p=P[i];
        int x=ask(1,2,p),y=ask(2,3,p);
        if(x==-1){answer(1); re;}
        if(y==-1){answer(2); re;}
        if(x==y) continue;
        k=(y-x+p)*ni[i]%p;
        b=(x-3*k+3*p)%p;
        break;
    }
    while(R-L>1){//对开区间 [l,R) 三等分 
        int x=(2ll*L+R)/3,y=(L+2ll*R)/3;
        //printf("[%d,%d] %d,%d\n",L,R,x,y);
        int w=ask(x,y,p);
        if(w==-1){answer(x);re;}
        int a0=(k*(x-2ll+y)+b)%p,a1=(k*(x-1ll+y)+b)%p,a2=(k*(x+0ll+y)+b)%p;
        if(w==a0) R=x;
        if(w==a1) L=x,R=y;
        if(w==a2) L=y;
    }
    answer(L);
}

signed main(){
    int T=read();
    while(T--) solve();
    return 0;
}