牛客练习赛105 F

引言

首杀，我的首杀……qwq

原来差点就 F 一血了……我 19:08:01 就提交了……8 min 就打完了……

结果 F 题让我发现我一直的异或卷积板子是假的……而且在平时只有一次卷积时可以证明不可能出锅……因为我最后一步的乘法打成加法了，然后平时这一位只可能是 $00$，$0+0=0\times 00+0=0\backslash times0$……

结果 $99$ 发罚时，一血不成反罚时，摆了摆了……

这个做法的时间复杂度是 $O(n\log v+q\log n\log v)O(n\backslash log\; v+q\backslash log\; n\backslash log\; v)$ 的，因此资瓷 $n\le 10^5,v\le 10^{18}n\backslash le10^5,v\backslash le10^\{18\}$，比某 FWT 集合对称差卷积不知道高到哪里去了……那个东西只能通过预处理前缀积、前缀 $00$ 个数做到 $O(nv\log v+qv)O(nv\backslash log\; v+qv)$……

这个做法的思想来源来自「2019 集训队互测 Day 2」序列。

以下是详细做法。

异或卷积

定义数列 $f,gf,g$ 的异或卷积为数列

$h_z={\sum }_{x\oplus y=z}{f}_x{g}_{y}h\_z=\backslash sum\_\{x\backslash oplus\; y=z\}f\_xg\_y$

不妨记为 $h=f{\times }_{\oplus }gh=f\backslash times\_\backslash oplus\; g$。

显然这个柿子的组合意义为枚举 $f,gf,g$ 对应下标异或值为 $zz$ 的方案数，其中 $f,gf,g$ 分别表示其作为子式时变量异或和为某值的方案数。

我们记 $f_{p,z}=[0\le z\le b_p]f\_\{p,z\}=[0\backslash le\; z\backslash le\; b\_p]$，显然答案即

$(f_l{\times }_{\oplus }{f}_{l+1}{\times }_{\oplus }{f}_{l+2}{\times }_{\oplus }\cdots f_r{)}_s(f\_l\backslash times\_\backslash oplus\; f\_\{l+1\}\backslash times\_\backslash oplus\; f\_\{l+2\}\backslash times\_\backslash oplus\backslash cdots\; f\_r)\_s$

如果我们使用 FWT + 线段树/猫树/优秀的前缀和技巧 + 单点查询优化，复杂度理论最优只能做到 $O(nv\log v+qv)O(nv\backslash log\; v+qv)$……

考虑怎么继续优化这个东西。

特殊形式的异或卷积

接下来的任务就是观察如何快速计算与记录这个异或卷积的结果了。

因为值域较大，所以异或卷积显然不能暴力使用基于快速沃尔什变换的集合对称差卷积实现，我们考虑观察性质。

不妨设在讨论范围内，一个数列非零值的下标总是小于 $2^{m}2^m$。

我们发现，对于数列 $f_{p}f\_p$，其前一半或后一半下标对应的值总是相等，另一半下标对应地递归满足相同性质。

简单讨论容易验证，异或卷积保持这个性质不变，因此对于两个满足该性质的数列 $f,gf,g$，$h=f{\times }_{\oplus }gh=f\backslash times\_\backslash oplus\; g$ 也满足这个性质。

于是我们可以使用 $m+1m+1$ 对数，来表示这样的一个数列（记录是前一半还是后一半为定值；记录具体是什么值）；对于这么一对数列的异或卷积，我们总可以在 $O(m)O(m)$ 的时间内实现，并返回一个仍保持此性质的数列。

因此，我们就可以优美地在 $O(\log v)O(\backslash log\; v)$ 的时间内单次合并了。

把这个东西搬上线段树，即可做到 $O(n\log v+q\log n\log v)O(n\backslash log\; v+q\backslash log\; n\backslash log\; v)$。

值得注意的是，如果把这个东西搬上猫树，复杂度理论可以做到 $O(n\log n\log v+q\log v)O(n\backslash log\; n\backslash log\; v+q\backslash log\; v)$。

Code

以下是核心代码。

const ullt Mod=1e9+7;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<std::pair<bol,modint> >vec;
typedef std::vector<modint>modvec;
const uint M=13;uint Len[M+1];
modvec User(vec a){
    modvec Ans(M+1);
    for(uint i=0;i<=M;i++)Ans[i]=a[i].second*Len[i];
    for(uint i=M;i;i--)Ans[i-1]+=Ans[i];
    return Ans;
}
vec mul(vec A,vec B){
    vec Ans(M+1);modvec UserA=User(A),UserB=User(B);
    for(uint i=0;i<M;i++){
        Ans[i].first=A[i].first==B[i].first;
        Ans[i+1].second+=Ans[i].second+A[i].second*B[i].second*Len[i];
        Ans[i].second+=A[i].second*UserB[i+1]+B[i].second*UserA[i+1];
    }
    Ans[M].second+=A[M].second*B[M].second;
    return Ans;
}
vec get(uint r){
    vec Ans(M+1);for(uint i=0;i<M;i++)if(r>=Len[i])Ans[i]={0,1},r-=Len[i];else Ans[i]={1,0};
    Ans[M].second=r;return Ans;
}
modint find(vec A,uint k){
    for(uint i=0;i<M;i++)if(A[i].first){
        if(k>=Len[i])return A[i].second;
    }else{
        if(k<Len[i])return A[i].second;
        k-=Len[i];
    }
    return A[M].second;
}
struct Seg{
    uint len;Seg*L,*R;vec v;
    Seg(uint*Bgn,uint*End):len(End-Bgn),L(NULL),R(NULL){
        if(len>1)L=new Seg(Bgn,Bgn+(len>>1)),R=new Seg(Bgn+(len>>1),End),v=mul(L->v,R->v);
        else v=get(*Bgn+1);
    }
    vec find(uint l,uint r){
        if(!l&&r==len)return v;
        if(l<(len>>1))
            if(r<=(len>>1))return L->find(l,r);
            else return mul(L->find(l,len>>1),R->find(0,r-(len>>1)));
        else return R->find(l-(len>>1),r-(len>>1));
    }
};
uint A[3005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    Len[M]=Len[M-1]=1;for(uint i=M-2;~i;i--)Len[i]=Len[i+1]*2;
    uint n,q;scanf("%u%u",&n,&q);for(uint i=0;i<n;i++)scanf("%u",A+i);
    Seg S(A,A+n);
    while(q--){
        uint l,r,v;
        scanf("%u%u%u",&l,&r,&v),l--;
        find(S.find(l,r),v).println();
    }
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。