2021“MINIEYE杯”中国大学生算法设计超级联赛（3）

好难啊，希望能补完。

拖了快一周了，补完了！

[1001 Bookshop]

solution

题面：给定一棵树，每个结点上有书，有价格，每次询问 到 ​ 的路径，给定初始钱，每次看到一本书如果钱够就买，问最后剩多少钱。

做法：树先转换为序列来看，那么难的就是维护买书条件。

如果我们希望能连续一段段维护的话，那么残酷的一大一小的数据就能把段数卡到 。

如果我们希望能让if x>a then x-=a 成为一个较为可维护的运算的话，那么在经过长时间的构造无果后，我们就只能放弃了这个做法。

于是，综合处理所有询问是唯一的办法。显然可以让所有 的数打一个 的标记。但随之而来产生了一个问题，我们想维护一个可以查询 且可以打标记的数据结构，容易想到平衡树。但在打标记之后，数的大小顺序是有可能发生改变的，所以好像这个结构不太好维护。

然后我们冷静一下，发现直接这些可能改变大小顺序的数的个数之和是一个可接受的范围。于是我们完善了我们的做法。

对 的数，我们显然不做理会。对 的数，我们强行拿出每一个数做一次减 。对 ​ 的数，我们打一次整体标记。​第一步和第三步操作是 的，而第二步操作中，由于我们对一个数减去了它至少一半的大小，那对一个数而言做暴力减法的次数就是 了。于是我们每次取出来再插回去的总复杂度就是 ​ 了。

至于放在树上，我们对树做一次重链剖分即可，每个询问就被拆成 ​ 段，每个节点维护每个询问的先后顺序即可。而买书操作与插入询问操作的复杂度是独立的，于是总时间复杂度就是 （设 同阶）。​

//2021.7.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,q;
    int p[N];
    vector<int> G[N];
    int dfn[N],low[N],idx,fa[N],top[N],sz[N],son[N],pos[N],dep[N];
    void dfs_sz(res x,res fax,res depx){
        fa[x]=fax,sz[x]=1,son[x]=0,dep[x]=depx;
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs_sz(tox,x,depx+1),sz[x]+=sz[tox];
            if(sz[son[x]]<sz[tox])son[x]=tox;
        }
    }
    void dfs_top(res x,res topx){
        pos[dfn[x]=++idx]=x,top[x]=topx;
        if(son[x])dfs_top(son[x],topx);
        for(auto tox:G[x]){
            if(tox==fa[x]||tox==son[x])continue;
            dfs_top(tox,tox);
        }
        low[x]=idx;
    }
    vector<int> ql[N],qr[N],qL[N],qR[N];
    //ql down to up
    //qr up
    //qL up to down
    //qR down
    int z[N];
    struct Treap{
        int son[2],laz,val,pri,fa;
    }tr[N];
    inline void change(const res &x,const res &v){
        tr[x].val+=v,tr[x].laz+=v;
    }
    inline void pushdown(const res &x){
        if(tr[x].laz)change(tr[x].son[0],tr[x].laz),change(tr[x].son[1],tr[x].laz),tr[x].laz=0;
    }
    inline int getnew(const res &x,const res &va){
        tr[x].son[0]=tr[x].son[1]=tr[x].laz=tr[x].fa=0,tr[x].val=va,tr[x].pri=rand();
        return x;
    }
    int merge(res x,res y){
        if(!x||!y)return x|y;
        pushdown(x),pushdown(y);
        if(tr[x].pri<tr[y].pri){
            tr[x].son[1]=merge(tr[x].son[1],y);
            tr[tr[x].son[1]].fa=x;
            return x;
        }
        else {
            tr[y].son[0]=merge(x,tr[y].son[0]);
            tr[tr[y].son[0]].fa=y;
            return y;
        }
    }
    void split(res rt,res &x,res &y,res k){
        if(!rt){x=y=0;return;}
        pushdown(rt);
        if(tr[rt].val<=k){
            x=rt;
            split(tr[rt].son[1],tr[rt].son[1],y,k);
        }
        else {
            y=rt;
            split(tr[rt].son[0],x,tr[rt].son[0],k);
        }
        tr[tr[rt].son[0]].fa=tr[tr[rt].son[1]].fa=rt;
    }
    int rt;
    inline void insert(const res &x){
        res a,b;
        split(rt,a,b,z[x]),rt=merge(merge(a,getnew(x,z[x])),b);
        tr[tr[tr[rt].son[0]].fa=tr[tr[rt].son[1]].fa=rt].fa=0;
    }
    int st[N],Top;
    inline void del(const res &x){
        res now=tr[x].fa;
        Top=0;
        while(now!=rt&&now)st[++Top]=now,now=tr[now].fa;
        pushdown(rt);
        for(res i=Top;i;i--)pushdown(st[i]);
        pushdown(x);
        z[x]=tr[x].val;
        if(x==rt)rt=merge(tr[x].son[0],tr[x].son[1]),tr[tr[tr[rt].son[0]].fa=tr[tr[rt].son[1]].fa=rt].fa=0;
        else {
            res Fa=tr[x].fa,d=(tr[Fa].son[1]==x);
            tr[tr[Fa].son[d]=merge(tr[x].son[0],tr[x].son[1])].fa=Fa;
        }
    }
    void mod(res x,const res &v){
        if(!x)return;
        z[x]=tr[x].val-v;
        pushdown(x);
        mod(tr[x].son[0],v),mod(tr[x].son[1],v);
        st[++Top]=x;
    }
    inline void modify(const res &x){
        res a,b,c,d;
        split(rt,a,b,x-1),split(b,c,d,2*x-1);
        if(d)change(d,-x);
        rt=merge(a,d);
        tr[tr[tr[rt].son[0]].fa=tr[tr[rt].son[1]].fa=rt].fa=0;
        Top=0,mod(c,x);
        for(res i=1;i<=Top;i++)insert(st[i]);
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),q=read(),rt=0;
            for(res i=1;i<=n;i++)p[i]=read(),vector<int>().swap(G[i]);
            for(res i=1;i<n;i++){
                res u=read(),v=read();
                G[u].pb(v),G[v].pb(u);
            }
            idx=0,dfs_sz(1,0,1),dfs_top(1,1);
            for(res i=1;i<=n;i++)vector<int>().swap(ql[i]),vector<int>().swap(qr[i]),vector<int>().swap(qL[i]),vector<int>().swap(qR[i]);
            for(res i=1;i<=q;i++){
                res x=read(),y=read();
                z[i]=read();
                while(top[x]!=top[y]){
                    if(dep[top[x]]>dep[top[y]])ql[dfn[x]].pb(i),qr[dfn[top[x]]].pb(i),x=fa[top[x]];
                    else qL[dfn[top[y]]].pb(i),qR[dfn[y]].pb(i),y=fa[top[y]];
                }
                if(dep[x]>dep[y])ql[dfn[x]].pb(i),qr[dfn[y]].pb(i);
                else qL[dfn[x]].pb(i),qR[dfn[y]].pb(i);
            }
            for(res i=n;i;i--){
                for(auto x:ql[i])insert(x);
                modify(p[pos[i]]);
                for(auto x:qr[i])del(x);
            }
            for(res i=1;i<=n;i++){
                for(auto x:qL[i])insert(x);
                modify(p[pos[i]]);
                for(auto x:qR[i])del(x);
            }
            for(res i=1;i<=q;i++)printf("%d\n",z[i]);
        }
    }
}

[1002 Destinations]

solution

题面：有 ​​ 个城市（一棵树）和 ​​ 个旅行者，每个旅行者从 ​​ 出发，他可以选择一个目的地，可供他选择的目的地分别为 ​​​，花费分别为 ​，旅行会经过最短路上所有城市，要求一种方案使得每个城市最多被一个人经过，求此时的最小花费（无解输出 ​​）。

做法：注意到一个人的三种路径都是共起点的，那么他选择且只能选择其中一条。这样的话，如果我们无视掉人这个东西，仅仅只看 ​ 条路径的话，无公共点的路径集合最多也只有 的大小。于是判断是否有解就等价于能否选出 ​ 条路径，更等价于选出最多的路径使得其数量大于等于 。于是，这题就等价于在选取路径条数最多的情况下，使权值和最小。

而选取无公共点的路径问题有一种常用解法是转成其对偶问题。于是我们构造矩阵：

$$c=\begin{bmatrix}(1,\inf-c_{1,1})\\ (1,\inf-c_{1,2})\\ (1,\inf-c_{1,3})\\(1,\inf-c_{2,1})\\...\\(1,\inf-c_{m,3})\end{bmatrix}\\\\ x=\begin{bmatrix}x_1\\ x_2\\...\\x_{3m}\end{bmatrix}\\\\ A=\begin{bmatrix}a_{1,1}&...&a_{3m,1}\\...&...&...\\a_{n,1}&...&a_{n,3m}\end{bmatrix}\\\\ b=\begin{bmatrix}1&1&...&1\end{bmatrix}$$

其中，二元组 ​​ 大小关系定义为 ​​。

其加减定义为 ，乘法定义为 。

​ 表示第 条路径是否选择， 表示第 条路径是否经过 点。

于是原问题就转换成了 ​​。

取其对偶问题，即 。

我们尝试理解 的含义， 实际上就是 ，而 是把一条路径上相关的 求和，要求大于等于这条路径的价值。那么我们就可以定义 表示 ​ 点的权值（二元组），原题就转换为在每条路径上的点的点权和大于等于这条路径价值的前提下，使所有点的权值和最小。这东西看似也不太好做，实则可以贪心。

我们从树的深处往浅处确认点权，考虑当前点 ​ 为一些路径端点的 ​​​​​，我们贪心地取当前点的点权为满足这些路径价值限制的最小值。为了证明这个贪心的正确性，我们考虑调整法。

方便说明，我们设满足端点的 为 的路径集合为 ​，一条路径表示为 ， 为价值限制， 为实际价值。

假设已经确认好所有点的点权了，若有一个点 的点权满足 中所有元素的 都大于 ​，我们不妨让 变成 。这样修改影响的是 的祖先节点。若祖先节点仍然满足限制，则这样修改更优。若有若干个点不满足，注意到 的祖先的祖先还是 的祖先，这意味着我们修改离 最近的祖先 成 ，就可以使 修改的影响被消除。而此时总价值不变，所以不劣。

根据上述调整法，我们证明了贪心的正确性。

考虑维护这个贪心，直接暴力可以用重链剖分 + 线段树做到 ，不过我们当然可以把路径点权和转到每个点到根的点权和，这样每次确认一个点修改就是这个点的子树罢了。利用 序转换为区间加求单点问题。线段树或差分 + 树状数组即可。时间复杂度 。

//2021.7.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
const int V=2000000;
namespace MAIN{
    vector<int> G[N];
    int n,m;
    Pair a[N];
    inline Pair operator + (const RG Pair &x,const RG Pair &y){
        return mp(x.fi+y.fi,x.se+y.se);
    }
    inline Pair operator - (const RG Pair &x,const RG Pair &y){
        return mp(x.fi-y.fi,x.se-y.se);
    }
    inline bool operator < (const RG Pair &x,const RG Pair &y){
    	return x.fi!=y.fi?x.fi<y.fi:x.se<y.se;
	}
    Pair val[N<<2];
    inline void change(const res &rt,const RG Pair &va){
        val[rt]=val[rt]+va;
    }
    inline void pushdown(const res &rt){
        change(rt<<1,val[rt]),change(rt<<1|1,val[rt]),val[rt]=mp(0,0);
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const RG Pair &va){
        if(L<=l&&r<=R){change(rt,va);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,va);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,va);
    }
    Pair query(res rt,res l,res r,const res &p){
        if(l==r)return val[rt];
        pushdown(rt);
        res mid=(l+r)>>1;
        if(p<=mid)return query(rt<<1,l,mid,p);
        return query(rt<<1|1,mid+1,r,p);
    }
    int dep[N],dfn[N],idx,low[N],F[N][21];
    void dfs(res x,res fax,res depx){
        F[x][0]=fax,dfn[x]=++idx,dep[x]=depx;
        for(res i=1;i<=20;i++)F[x][i]=F[F[x][i-1]][i-1];
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs(tox,x,depx+1);
        }
        low[x]=idx;
    }
    inline int get_lca(res x,res y){
        if(dep[x]<dep[y])swap(x,y);
        res d=dep[x]-dep[y];
        for(res i=20;~i;i--)if(d&(1<<i))x=F[x][i];
        if(x==y)return x;
        for(res i=20;~i;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
        return F[y][0];
    }
    struct P{
        int u,v;
		LL w;
        P() {}
        P(res u,res v,RG LL w):u(u),v(v),w(w) {}
    };
    vector<P> tr[N];
    void solve(res x,res fax){
        a[x]=mp(0,0);
        for(auto tox:G[x]){
            if(tox==fax)continue;
            solve(tox,x);
        }
        for(auto t:tr[x]){
            RG Pair y=query(1,1,n,dfn[t.u])+query(1,1,n,dfn[t.v]);
            if(y+a[x]<mp(1,t.w))a[x]=mp(1,t.w)-y;
        }
        modify(1,1,n,dfn[x],low[x],a[x]);
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),m=read(),idx=0;
            for(res i=1;i<=n;i++)for(res j=0;j<=20;j++)F[i][j]=0;
            for(res i=1;i<=n;i++)vector<int>().swap(G[i]),vector<P>().swap(tr[i]);
            for(res i=1;i<=n*4;i++)val[i]=mp(0,0);
            for(res i=1;i<n;i++){
                res u=read(),v=read();
                G[u].pb(v),G[v].pb(u);
            }
            dfs(1,0,1);
            for(res i=1;i<=m;i++){
                res s=read(),e=read(),c=read(),lca=get_lca(s,e);
                tr[lca].pb(P(s,e,V-c));
                e=read(),c=read(),lca=get_lca(s,e);
                tr[lca].pb(P(s,e,V-c));
                e=read(),c=read(),lca=get_lca(s,e);
                tr[lca].pb(P(s,e,V-c));
            }
            solve(1,0);
            RG Pair ret=mp(0,0);
            for(res i=1;i<=n;i++)ret=ret+a[i];
            if(ret.fi<m)puts("-1");
			else printf("%lld\n",-ret.se+1ll*V*m);
        }
    }
}

[1003 Forgiving Matching]

solution

题面：两个串匹配当且仅当长度相同，且对应位置上不同的字符 个，可以通配。给定模板串和询问串，对每个 ​​ 求匹配数。字符集是。

做法：字符串匹配，经典做法就是按每个字符算一遍，取 表示当前位置是不是该字符，然后 ​ 取反后卷积算出匹配个数。加上通配符，就是在前面都把通配符算成那个字符，最后再减去通配符匹配通配符的个数即可。时间复杂度 。

事实证明，FFT 把 NTT 在这种情况下暴打了，下面的 NTT 代码过不了，后来去贺了个 FFT 才能过。

//2021.7.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e6+10;
namespace MAIN{
    char s[N],t[N];
    struct Poly{
        int pw[N],pos[N],p,Og[N];
        inline void init(const res &n){
            pw[0]=1;
            for(res i=1;;i++){
                pw[i]=pw[i-1]<<1;
                if(pw[i]>n)break;
            }
        }
        inline void DFT(RG poly &A){
            for(res i=0;i<pw[p];i++)if(i<pos[i])swap(A[i],A[pos[i]]);
            for(res i=0;i<=p;i++){
                res wn=qpow(G,(kcz-1)/(pw[i+1]));
                Og[0]=1;
                for(res j=1;j<pw[i];j++)Og[j]=mul(Og[j-1],wn);
                for(res j=0;j<pw[p];j+=pw[i+1])
                    for(res k=0;k<pw[i]&&j+pw[i]+k<pw[p];k++){
                        res x=A[j+k],y=mul(A[j+pw[i]+k],Og[k]);
                        A[j+k]=Add(x,y),A[j+pw[i]+k]=Add(x,-y);
                    }
            }
        }
        inline void IDFT(RG poly &A){
            for(res i=0;i<pw[p];i++)if(i<pos[i])swap(A[i],A[pos[i]]);
            for(res i=0;i<=p;i++){
                res wn=qpow(GI,(kcz-1)/(pw[i+1]));
                Og[0]=1;
                for(res j=1;j<pw[i];j++)Og[j]=mul(Og[j-1],wn);
                for(res j=0;j<pw[p];j+=pw[i+1])
                    for(res k=0;k<pw[i]&&j+pw[i]+k<pw[p];k++){
                        res x=A[j+k],y=mul(A[j+pw[i]+k],Og[k]);
                        A[j+k]=Add(x,y),A[j+pw[i]+k]=Add(x,-y);
                    }
            }
            res INV=qpow(pw[p],kcz-2);
            for(res i=0;i<pw[p];i++)A[i]=mul(A[i],INV);
        }
        inline int pre(const res &n){
            p=0;
            while(pw[p]<=n)p++;
            for(res i=0;i<pw[p];i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(p-1));
            return pw[p];
        }
        inline poly FFT(RG poly &A,RG poly &B){
            RG poly C(pw[p]);
            DFT(A),DFT(B);
            for(res i=0;i<pw[p];i++)C[i]=mul(A[i],B[i]);
            IDFT(C);
            return C;
        }
    }T;
    int n,m;
    int ans[N],cnt[N];
    inline void MAIN(){
        res aqua=read();
        T.init(800000);
        while(aqua--){
            n=read(),m=read(),scanf("%s",s),scanf("%s",t);
            res l=T.pre(n+m);
            RG poly A(l),B(l);
            for(res i=0;i<=n-m;i++)ans[i]=cnt[i]=0;
            for(res i='0';i<='9';i++){
                for(res j=0;j<l;j++)A[j]=B[j]=0;
                for(res j=0;j<n;j++)A[j]=(s[j]==i||s[j]=='*');
                for(res j=0;j<m;j++)B[l-j==l?0:l-j]=(t[j]==i||t[j]=='*');
                A=T.FFT(A,B);
                for(res j=0;j<=n-m;j++)add(ans[j],A[j]);
            }
            for(res j=0;j<l;j++)A[j]=B[j]=0;
            for(res j=0;j<n;j++)A[j]=(s[j]=='*');
            for(res j=0;j<m;j++)B[l-j==l?0:l-j]=(t[j]=='*');
            A=T.FFT(A,B);
            for(res j=0;j<=n-m;j++)add(ans[j],kcz-mul(9,A[j]));
            for(res i=0;i<=n-m;i++)cnt[ans[i]]++;
            res sum=0;
            for(res i=m;~i;i--)printf("%d\n",sum+=cnt[i]);
        }
    }
}

[1004 Game on Plane]

solution

题面：给定 条直线，，A 选其中 个，B 再画一个直线，B 想让画出的与选出的直线不平行的（相交或重合）尽量少，A 希望尽量多，对每个 ​ 求结果。

做法：签到题。肯定想的是选尽量不同的斜率，随便维护一下即可。我实现的复杂度是 。

//2021.7.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    Pair a[N];
    map<Pair,int> M;
    int b[N],bx;
    inline void MAIN(){
        res T=read();
        while(T--){
            map<Pair,int>().swap(M);
            res n=read();
            for(res i=1;i<=n;i++){
                res x0=read(),y0=read(),x1=read(),y1=read();
                res g=__gcd(x1-x0,y1-y0);
                a[i]=mp((x1-x0)/g,(y1-y0)/g);
                if(a[i].fi<0)a[i].fi=-a[i].fi,a[i].se=-a[i].se;
                if(a[i].fi==0)a[i].se=abs(a[i].se);
                M[a[i]]++;
            }
            bx=0;
            for(auto x:M)b[++bx]=x.se;
            sort(b+1,b+bx+1);
            res mx=0;
            res j=bx+1,st=1;
            for(res i=1;i<=n;i++){
                if(j==bx+1){
                    j=st,mx++;
                    while(b[j]<mx)j++;
                    st=j;
                }
                j++;
                printf("%d\n",i-mx);
            }
        }
    }
}

[1005 Kart Race]

solution

题面：你有 个点 ，价值为 ，有 条单向边从 连向 ，满足 。你选取一个点可获得 的钱，对于所有可能的从 到 ​​​ 的路径上最多只能选取一个点，问最大价值，并输出字典序最小的方案。保证图为平面图。

做法：首先题意可以转换为选出若干个两两不可达的点使得在价值和最大的前提下，使字典序最小。

由于这是张平面有向无环图，我们可以利用 ​​ 序快速判断两点是否可达。

即在 时，对于一个点的出边，我们先考虑顺时针遍历，记此时出栈序为 。再考虑逆时针遍历，记此时出栈序为 。有一个结论是当 可以到 时，当且仅当 且 。这个结论也是容易证明的。若 ，则 不可能到达 。另一方面， 当且仅当 可以到达 或者 相当于 在 的顺时针方向。于是 两者一起限制就会保证 可以到达 了。

于是题意就转换为选出一组点使得 递增 ​ 递减，同时在价值和最大的前提下，使字典序最小。第一个限制是个经典的二维偏序，排序一维，另一维树状数组维护即可。价值和最大直接处理。字典序最小的条件难处理一点，我们会发现在用树状数组处理另一维的时候， 每次执行的是选取一组数，再加入一个点入这组数，总修改量是 ​ 级别的。于是我们考虑状压，因为修改量比较小，所以我们可以用可持久化线段树来维护状压的状态，每次转移就是在可持久化线段树上给两者比大小，这是 的。而修改也是 的。再套一个树状数组，总时间复杂度就是 的了。

不知道为什么评测机变奇怪了，不能忽略行末空格了，写的时候稍微注意点。

//2021.7.31 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,m;
    struct P{
        int x,y,w;
        P() {}
        P(res x,res y,res w):x(x),y(y),w(w) {}
        inline void init(){
            x=read(),y=read(),w=read();
        }
    }p[N];
    inline LL operator ^ (const RG Pair &x,const RG Pair &y){
        return 1ll*x.fi*y.se-1ll*x.se*y.fi;
    }
    int I;
    vector<int> G[N];
    inline bool cmp(const res &A,const res &B){
        return (mp(p[I].x-p[A].x,p[I].y-p[A].y)^mp(p[I].x-p[B].x,p[I].y-p[B].y))>0;
    }
    int a[N],b[N],idx,vis[N],pos[N];
    void dfs_c(res x){
        if(vis[x])return;
        vis[x]=1;
        for(auto tox:G[x])dfs_c(tox);
        a[x]=++idx;
    }
    void dfs_d(res x){
        if(vis[x])return;
        vis[x]=1;
        for(auto tox:G[x])dfs_d(tox);
        pos[b[x]=++idx]=x;
    }
    int ls[N*30],rs[N*30],tot;
    void insert(res &rt,res RT,res l,res r,const res &p){
        rt=++tot;
        ls[rt]=ls[RT],rs[rt]=rs[RT];
        if(l==r)return;
        res mid=(l+r)>>1;
        if(p<=mid)insert(ls[rt],ls[RT],l,mid,p);
        else insert(rs[rt],rs[RT],mid+1,r,p);
    }
    inline bool ck(res rt0,res rt1){
        if(rt0==rt1)return 0;
        res l=1,r=n;
        while(l<r){
            res mid=(l+r)>>1;
            if(ls[rt0]==ls[rt1])l=mid+1,rt0=rs[rt0],rt1=rs[rt1];
            else r=mid,rt0=ls[rt0],rt1=ls[rt1];
        }
        return rt0<rt1;
    }
    struct T{
        LL fi;
        int se;
        T() {}
        T(RG LL fi,res se):fi(fi),se(se) {}
        inline bool operator < (const RG T &A) const {
            if(fi<A.fi)return 1;
            if(fi>A.fi)return 0;
            return ck(se,A.se);
        }
    };
    T tr[N];
    inline void modify(const res &x,const RG T &y){
        for(res i=x;i<=n;i+=lowbit(i))tr[i]=max(tr[i],y);
    }
    inline T query(const res &x){
        RG T ret=T(0,0);
        for(res i=x;i;i-=lowbit(i))ret=max(ret,tr[i]);
        return ret;
    }
    int Ans[N],cnt; 
    void dfs(res rt,res l,res r){
        if(!rt)return;
        if(l==r){Ans[++cnt]=l;return;}
        res mid=(l+r)>>1;
        dfs(ls[rt],l,mid),dfs(rs[rt],mid+1,r);
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),m=read(),tot=0;
            for(res i=1;i<=n;i++)p[i].init(),vector<int>().swap(G[i]),tr[i]=T(0,0);
            for(res i=1;i<=m;i++){
                res u=read(),v=read();
                G[u].pb(v);
            }
            for(res i=1;i<=n;i++)I=i,sort(G[i].begin(),G[i].end(),cmp);
            for(res i=1;i<=n;i++)vis[i]=0;
            idx=0,dfs_c(1);
            for(res i=1;i<=n;i++)vis[i]=0,reverse(G[i].begin(),G[i].end());
            idx=0,dfs_d(1);
            RG T ans=T(0,0);
            for(res o=n;o;o--){
                res x=pos[o];
                RG T ret=query(a[x]);
                ret.fi+=p[x].w,insert(ret.se,ret.se,1,n,x),ans=max(ans,ret),modify(a[x],ret);
            }
            printf("%lld\n",ans.fi),cnt=0;
            dfs(ans.se,1,n);
            for(res i=1;i<=cnt;i++)printf("%d%c",Ans[i],(i<cnt)?' ':'\n');
        }
    }
}

[1006 New Equipments II]

solution

题面：有 个人和 件物品，每个人和物品分别有个价值 ，第 个人修第 个物品的价值是 ，一个人只能修一个物品，有 个限制是第 个人不能修第 件物品，问对于每一个 ​，最大价值为多少。​ 表示当前要修几个物品。

做法：容易建出费用流模型，于是考虑模拟费用流。

由于这张图只有四层，而且是首尾两层与中间连接的时候才有费用，那么当我们选择一次配对 ​ 后，第二层与 有边的点就会和第三层与 有边的点连通（这可以手动模拟费用流看一次），于是暴力地，我们添加这些新的可行匹配进堆里，每次取最大即可，时间复杂度 ​。

好像多了个这个 ​​ 就跑不过了啊。那我们考虑补图上的情况，每次在补图上暴力找边的复杂度是 的，再反过来维护原图情况，这样就去掉 了。不过我已经不想写了，就去贺了个代码。

下面是带 的代码。

//2021.8.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e4+5;
namespace MAIN{
    int n,m;
    Pair edge[N];
    int a[N],b[N];
    int ed[4000+5][4000+5];
    struct P{
        int u,v,w;
        P() {}
        P(res u,res v,res w):u(u),v(v),w(w) {}
        inline bool operator < (const RG P &A) const {
            return w<A.w;
        }
    };
    priority_queue<P> Q;
    int visa[N],visb[N],fl[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),m=read();
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)ed[i][j]=0;
            for(res i=1;i<=n;i++)a[i]=read(),visa[i]=0;
            for(res i=1;i<=n;i++)b[i]=read(),visb[i]=0;
            for(res i=1;i<=m;i++){
                res u=read(),v=read();
                edge[i]=mp(u,v),ed[u][v]=1,fl[i]=0;
            }
            priority_queue<P>().swap(Q);
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)if(!ed[i][j])Q.push(P(i,j,a[i]+b[j]));
            RG LL ans=0;
            for(res Case=1;Case<=n;Case++){
                while((visa[Q.top().u]||visb[Q.top().v])&&!Q.empty())Q.pop();
                if(Q.empty()){
                    for(res _=Case;_<=n;_++)puts("-1");
                    break;
                }
                res u=Q.top().u,v=Q.top().v;
                ans+=Q.top().w;
                Q.pop();
                visa[u]=visb[v]=1;
                for(res i=1;i<=m;i++){
                    if(fl[i])continue;
                    if(!ed[edge[i].fi][v]&&!ed[u][edge[i].se]){
                        fl[i]=1;
                        ed[edge[i].fi][edge[i].se]=0;
                        if(visa[edge[i].fi]||visb[edge[i].se])continue;
                        Q.push(P(edge[i].fi,edge[i].se,a[edge[i].fi]+b[edge[i].se]));
                    }
                }
                printf("%lld\n",ans);
            }
        }
    }
}

[1007 Photoshop Layers]

solution

题面：有 ​​​​​ 个四元组序列 ​​​​​​​，每次询问 ​​​​​，从 ​​​​​ 开始用三元组 ​​​​​ 叠加四元组，每遇到一个 ​​​​​​ 则令当前三元组为 ​​​​，每遇到一个 ​​​​ 则令三元组为 。求最后的三元组。​​​​

做法：每次询问找到最右边的 ，然后取 操作统一放在最后，那么只用维护个前缀和了。时间复杂度 。

原来输出十六进制有特殊的方法啊，我完全不知道哎。

//2021.7.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int n,q;
    char str[N];
    struct P{
        int x,y,z;
        P() {}
        P(res x,res y,res z):x(x),y(y),z(z) {}
    }a[N];
    inline P operator + (const RG P &A,const RG P &B){
        return P(A.x+B.x,A.y+B.y,A.z+B.z);
    }
    inline P operator - (const RG P &A,const RG P &B){
        return P(A.x-B.x,A.y-B.y,A.z-B.z);
    }
    inline int get(const RG char &a){
        if('0'<=a&&a<='9')return a-'0';
        if(a=='A')return 10;
        if(a=='B')return 11;
        if(a=='C')return 12;
        if(a=='D')return 13;
        if(a=='E')return 14;
        if(a=='F')return 15;
    }
    int b[N],bx;
    inline int ck(const res &p){
        res l=1,r=bx,ret=0;
        while(l<=r){
            res mid=(l+r)>>1;
            if(b[mid]<=p)l=mid+1,ret=mid;
            else r=mid-1;
        }
        return ret;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),q=read(),bx=0;
            for(res i=1;i<=n;i++){
                res op=read();
                scanf("%s",str+1);
                res x=get(str[1])*16+get(str[2]);
                res y=get(str[3])*16+get(str[4]);
                res z=get(str[5])*16+get(str[6]);
                if(op==1){
                    b[++bx]=i,a[i]=P(x,y,z);
                }
                else a[i]=P(x,y,z);
            }
            for(res i=1;i<=n;i++)a[i]=a[i]+a[i-1];
            while(q--){
                res l=read(),r=read();
                res p=b[ck(r)];
                if(!p||p<l){
                    RG P o=a[r]-a[l-1];
                    printf("%02X%02X%02X\n",min(o.x,255),min(o.y,255),min(o.z,255));
                }
                else {
                    RG P o=a[r]-a[p-1];
                    printf("%02X%02X%02X\n",min(o.x,255),min(o.y,255),min(o.z,255));
                }
            }
        }
    }
}

[1008 Restore Atlantis II]

solution

题面：给 ​ 个矩形（平行于坐标系），每次询问求 ​​ 编号之内的矩形并的面积。保证数据随机。

做法：考虑一维情况，我们发现随机数据下许多线段会被其他线段所包含，于是可用线段会比较少。同样地，二维也是如此。我们维护每个 坐标下可以向左延伸的 区间（有若干个），我们发现相邻的 对应的 线段组相同的会比较多，同时 线段组大小也比较小（可以将所有相交区间合并），所以实际可用的比较少，大概只有几十个？ 没仔细算，反正我开了 ​ 是可以过的。

然后有了这个条件怎么办呢？设线段组大小乘不同线段组的级别是 ​，我们考虑线段树，这样每次合并两个区间的复杂度是 ​ （利用归并排序）的。于是我们就做到了 ​ 预处理，询问 ​​。

然而出题人卡了这个做法。我们发现本题没有修改只有询问，所以考虑 ST 表，这样就是 预处理， 询问，比线段树还要烂。

我们再优化，考虑四毛子算法，即分块，但分块大小为 ​​​。由于是随机数据，我们发现一次询问在同一个块内的期望次数是 ​​​ 的，因此我们可以暴力合并。而不在一个块里的时候，我们维护每个块的前缀线段组并，后缀线段组并，以及用 ST 表维护一个范围块内的线段组并。这个预处理复杂度是 ​​​​ 即 ​ 的，而询问则是 ​​ 的（我们只用合并后缀 + 中间整块 + 前缀，而中间整块利用 ST 表合并两段）。综上，总复杂度就是 ​ 即 。

实际上有点小卡常，感觉是我实现比较烂了。。。

//2021.8.2 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,q;
    typedef vector<Pair> seg;
    typedef pair<int,seg> pair;
    typedef vector<pair> T;
    inline seg Merge(const RG seg &A,const RG seg &B){
        static Pair C[150+10];
        if(A.empty())return B;
        if(B.empty())return A;
        res l=0,r=0,sza=int(A.size())-1,szb=int(B.size())-1,sz=0;
        while(l<=sza&&r<=szb){
            if(A[l].fi<B[r].fi)C[sz++]=A[l],l++;
            else C[sz++]=B[r],r++;
        }
        while(l<=sza)C[sz++]=A[l],l++;
        while(r<=szb)C[sz++]=B[r],r++;
        RG seg D;
        D.pb(C[0]);
        res j=0;
        for(res i=1;i<sz;i++){
            if(D[j].se>=C[i].fi)D[j].se=max(D[j].se,C[i].se);
            else D.pb(C[i]),j++;
        }
        return D;
    }
    inline T merge(const RG T &A,const RG T &B){
        static pair C[150+10];
        res sza=int(A.size())-1,szb=int(B.size())-1,sz=0;
        res l=0,r=0;
        while(l<=sza&&r<=szb){
            if(A[l].fi<B[r].fi)C[sz++]=mp(A[l].fi,Merge(A[l].se,B[r].se)),l++;
            else if(A[l].fi>B[r].fi)C[sz++]=mp(B[r].fi,Merge(B[r].se,A[l].se)),r++;
            else C[sz++]=mp(A[l].fi,Merge(A[l].se,B[r].se)),l++,r++;
        }
        while(l<=sza)C[sz++]=A[l],l++;
        while(r<=szb)C[sz++]=B[r],r++;
        RG T D;
        D.pb(C[0]);
        res j=0;
        for(res i=1;i<sz;i++){
            if(D[j].se==C[i].se)D[j].fi=C[i].fi;
            else D.pb(C[i]),j++;
        }
        return D;
    }
    inline LL query(const RG T &A){
        RG LL ret=0;
        res sz=int(A.size())-1;
        for(res i=1;i<=sz;i++){
            res tmp=0;
            for(auto x:A[i].se)tmp+=x.se-x.fi;
            ret+=1ll*tmp*(A[i].fi-A[i-1].fi);
        }
        return ret;
    }
    const int K=7;
    int pl[N],pr[N],pa[N];
    T pre[N],suf[N],a[N];
    inline T re(){
        RG T ret;
        res xl=read(),yl=read(),xr=read(),yr=read();
        RG seg A;
        ret.pb(mp(xl,A));
        A.pb(mp(yl,yr));
        ret.pb(mp(xr,A));
        return ret;
    }
    int Lg[N];
    T st[(N>>K)+5][14];
    inline void MAIN(){
        for(res i=2;i<=N-10;i++)Lg[i]=Lg[i>>1]+1;
        res Case=read();
        while(Case--){
            n=read(),q=read();
            for(res i=1;i<=n;i++)pr[(i>>K)+1]=i;
            for(res i=n;i;i--)pl[(i>>K)+1]=i;
            for(res i=1;i<=n;i++)pa[i]=(i>>K)+1;
            for(res i=1;i<=n;i++)a[i]=re();
            res sz=(n>>K)+1;
            for(res p=1;p<=sz;p++){
                pre[pl[p]]=a[pl[p]];
                for(res i=pl[p]+1;i<=pr[p];i++)pre[i]=merge(pre[i-1],a[i]);
                suf[pr[p]]=a[pr[p]];
                for(res i=pr[p]-1;i>=pl[p];i--)suf[i]=merge(suf[i+1],a[i]);
                st[p][0]=suf[pl[p]];
            }
            for(res j=1;j<=13;j++)for(res i=1;i+(1<<j)-1<=sz;i++)st[i][j]=merge(st[i][j-1],st[i+(1<<(j-1))][j-1]);
            while(q--){
                res l=read(),r=read();
                if(pa[l]+1<pa[r]){
                    res L=pa[l],R=pa[r],k=Lg[R-L-1];
                    printf("%lld\n",query(merge(merge(suf[l],pre[r]),merge(st[L+1][k],st[R-(1<<k)][k]))));
                }
                else if(pa[l]==pa[r]){
                    RG T ret=a[l];
                    for(res i=l+1;i<=r;i++)ret=merge(ret,a[i]);
                    printf("%lld\n",query(ret));
                }
                else printf("%lld\n",query(merge(suf[l],pre[r])));
            }
        }
    }
}

[1009 Rise in Price]

solution

题面： 的网格，每个位置有一个 ，从 开始，只能走 ，希望规划一条路径，使得 ​ 最大。保证数据随机。

做法：考虑一个暴力， 表示走到 时的二元组集合 ，显然二维都更大的一定更优。

接下来想数据随机要怎么样，猜测一下就是二维都更大的数比较多，所以二元组集合大小比较小，暴力转移就好了。

复杂度 。

//2021.8.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
    int n;
    vector<Pair> f[N][N];
    int a[N][N],b[N][N];
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read();
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)a[i][j]=read();
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)b[i][j]=read();
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)vector<Pair>().swap(f[i][j]);
            f[1][1].pb(mp(a[1][1],b[1][1]));
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++){
                if(i==1&&j==1)continue;
                if(i==1)for(auto x:f[i][j-1])f[i][j].pb(mp(x.fi+a[i][j],x.se+b[i][j]));
                else if(j==1)for(auto x:f[i-1][j])f[i][j].pb(mp(x.fi+a[i][j],x.se+b[i][j]));
                else {
                    vector<Pair> c,A;
                    res l=0,r=0,la=int(f[i-1][j].size()-1),lb=int(f[i][j-1].size()-1);
                    while(l<=la&&r<=lb){
                        if(f[i-1][j][l]>f[i][j-1][r])c.pb(f[i-1][j][l]),l++;
                        else c.pb(f[i][j-1][r]),r++;
                    }
                    while(l<=la)c.pb(f[i-1][j][l]),l++;
                    while(r<=lb)c.pb(f[i][j-1][r]),r++;
                    l=1,la=int(c.size()-1);
                    A.pb(c[0]);
                    RG LL mx=c[0].se;
                    while(l<=la)if(mx>=c[l].se)l++;else mx=max(mx,c[l].se),A.pb(c[l++]);
                    for(auto x:A)f[i][j].pb(mp(x.fi+a[i][j],x.se+b[i][j]));
                }
            }
            RG LL ans=0;
            for(auto x:f[n][n])ans=max(ans,x.fi*x.se);
            printf("%lld\n",ans);
        }
    }
}

[1010 Road Discount]

solution

题面：给 条边，每条边连接 ，原价为 ，打折后为 ，然后希望把原图连成一棵树。对 分别输出最小价格。​ 表示最多可以打折的边数。

做法：生成树特殊边问题大部分的答案都具有凸性，于是我们考虑 wqs 二分。

对每个 ​ 进行 wqs 二分，即将打折边的边权减去二分的斜率，然后跑一棵最小生成树即可，这样的复杂度是 ​​的。

注意到每次多一条边打折时，我们最多改变一条边，这可以很轻松证明，因为若改变的不止一条边的话，那么在之前改变的时候就会选择那条边了，由此反证说明最多改变一条边。那么我们总共会用到的边将只有不打折的最小生成树树边以及全打折的最小生成树的树边，于是我们可以将 变成 ，总复杂度就是 了。

注意到边权实际会很小，而斜率只会是 ​，那么斜率的范围只会是 ​。于是我们从大到小枚举斜率，直接刻画答案的下凸壳。每次取到的时候只会影响向右的未取到的区间，​因此我们暴力取 即可，这样同时也规避了答案非严格下凸的情况。时间复杂度就变成 了。

其实，就算我们不考虑 wqs 二分，直接维护每次只会更新一条边这个操作也是可行的。这等价于我们枚举一条边，然后找到两个连通块间的最短边。这两个操作可以一起来，即快速维护两棵树的图的不同连通块间的最大边权减最小边权。这个东西可以利用 LCT 维护，时间复杂度是 ​​。考场上 ljc 实现的是这个。

下面代码是 wqs 二分。

//2021.8.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int n,m;
    struct E{
        int u,v,w;
        E() {}
        E(res u,res v,res w):u(u),v(v),w(w) {}
        inline bool operator < (const RG E &B) const {
            return w<B.w;
        }
    }ed0[N],ed1[N],e0[N],e1[N];
    struct ED{
        E x;
        int op;
        ED() {}
        ED(RG E x,res op):x(x),op(op) {}
    }edge[N];
    int fa[N];
    inline int find(res x){
        while(x!=fa[x])x=fa[x]=fa[fa[x]];
        return x;
    }
    int f[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),m=read();
            for(res i=1;i<=n;i++)fa[i]=i;
            for(res i=1;i<=m;i++){
                res u=read(),v=read(),c=read(),d=read();
                ed0[i]=E(u,v,c),ed1[i]=E(u,v,d);
            }
            sort(ed0+1,ed0+m+1),sort(ed1+1,ed1+m+1);
            for(res i=1;i<=n;i++)fa[i]=i;
            res cnt=0;
            for(res i=1;i<=m;i++){
                res fu=find(ed0[i].u),fv=find(ed0[i].v);
                if(fu==fv)continue;
                e0[++cnt]=ed0[i],fa[fu]=fv;
            }
            for(res i=1;i<=n;i++)fa[i]=i;
            cnt=0;
            for(res i=1;i<=m;i++){
                res fu=find(ed1[i].u),fv=find(ed1[i].v);
                if(fu==fv)continue;
                e1[++cnt]=ed1[i],fa[fu]=fv;
            }
            for(res i=0;i<n;i++)f[i]=inf;
            for(res k=1000;k>=-1000;k--){
                for(res i=1;i<n;i++)e1[i].w-=k;
                res l=1,r=1;
                while(l<n&&r<n){
                    if(e0[l].w<=e1[r].w)edge[l+r-1]=ED(e0[l],0),l++;
                    else edge[l+r-1]=ED(e1[r],1),r++;
                }
                while(l<n)edge[l+r-1]=ED(e0[l],0),l++;
                while(r<n)edge[l+r-1]=ED(e1[r],1),r++;
                for(res i=1;i<=n;i++)fa[i]=i;
                res sum=0,ret=0;
                for(res i=1;i<=2*n-2;i++){
                    res fu=find(edge[i].x.u),fv=find(edge[i].x.v);
                    if(fu==fv)continue;
                    sum+=edge[i].op,ret+=edge[i].x.w,fa[fu]=fv;
                }
                for(res i=sum;i<n;i++)if(f[i]==inf)f[i]=ret+i*k;
                for(res i=1;i<n;i++)e1[i].w+=k;
            }
            for(res i=0;i<n;i++)printf("%d\n",f[i]);
        }
    }
}

[1011 Segment Tree with Pruning]

solution

题面：给出 ，和

Node * build ( long long l , long long r ) {
        Node * x = new ( Node );
        if (r - l + 1 <= k) return x;
        long long mid = ( l + r ) / 2;
        x -> lchild = build ( l , mid );
        x -> rchild = build ( mid + 1, r );
        return x;
 }

问节点数。

做法：显然答案只跟长度有关，而每次是长度除以 ，那么直接暴力的复杂度显然也是 的，加个 map 维护也无所谓了。时间复杂度 。​

//2021.8.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e4+5;
namespace MAIN{
    map<LL,LL> M;
    LL k;
    LL solve(RG LL n){
        if(n<=k)return 1;
        if(M[n])return M[n];
        RG LL mid=(n+1)>>1;
        return M[n]=solve(mid)+solve(n-mid)+1;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            RG LL n=Read();
            k=Read();
            map<LL,LL>().swap(M);
            printf("%lld\n",solve(n));
        }
    }
}

[1012 Tree Planting]

solution

题面：给你 ​​​ 个数 ​​​，你决定每个 ​​​，需要满足

1. 至少一个 ​​​

2. ​​​ 和 ​​​ 不能同时成立

3. ​​​ 和 ​​​ 不能同时成立（​​​ 给定）

   最终价值为所有 ​​​​ 的 ​​​​ 的 ​​​​ 之积，求所有方案的价值之和。

做法：考场上某人翻错了题目，我先不谈。

首先有一种经典的想法，就是把 号结点放在 ​​ 上，这样的好处就是题意被转换成了相邻点不能同时染色，而且第一行向后退一步与最后一行的那格不能同时染色（请脑补一下，不太会用文字表述）。这样就能写出一个​​​ 的大暴力，即你先枚举完第一行的状态，然后维护当前点同一行左边的与上一行右边的状态，即俗称的轮廓线，拿这个 dp 就可以了。

另一方面，更容易想到的暴力是令 表示当前 dp 到 点，前面 ​ 个点状态为 的价值之和。转移就直接转移了，这样复杂度是 。

我们很容易想到数据分治一下，于是复杂度优化成 。

以上差不多是我考场上的想法，接下来就让我猝不及防了。

如果你什么都不知道，抱着冲一发的心态随手写了个暴力，想着剪枝，于是把无用态即转移不到的状态全部去掉，然后直接交一发，那么就会意外地发现自己竟然过了此题。

这是为什么呢？我们观察每次的状态意味着什么，我们发现每种状态都至少要满足相邻点的颜色不能相同，哪怕是轮廓线那里的状态，也要满足转折点与相邻都不相同，即多一个点的相邻点颜色不同。这是啥？这等价于一条链上相邻点颜色不同，即链的点独立集，有趣的是，​​​​ 个点的链的点独立集数量为斐波那契数列的第 ​​​ 项（这可以写出递推式来递推出），于是数量就是 ​ 级别的，总复杂度就被剪枝到 ​​ 了。​​​​

不知道为什么我代码常数特别大，有没有小哥哥能帮我查查错啊/ll

//2021.8.2 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=300+10;
namespace MAIN{
    int n,k;
    int w[N];
    const int HashMod=100007;
    struct HashTable{
        struct E{
            int nxt,v,val;
            E() {}
            E(res nxt,res v,res val):nxt(nxt),v(v),val(val) {}
        }edge[300000+10];
        int head[HashMod],cnt,now,non;
        inline void ADD(const res &u,const res &v,const res &w){
            edge[++cnt]=E(head[u],v,w),head[u]=cnt;
        }
        inline void Clear(){
            memset(head,0,sizeof(head)),cnt=now=0,non=-1;
        }
        inline int &Query(const res &x){
            res s=x%HashMod;
            for(res i=head[s];i;i=edge[i].nxt)if(edge[i].v==x)return edge[i].val;
            return non;
        }
        inline void Hash(const res &x,const res &k){
            res &o=Query(x);
            if(o==-1){
                res s=x%HashMod;
                ADD(s,x,k);
            }
            else add(o,k);
        }
        inline Pair get(){
            now++;
            if(now>cnt)return mp(-1,-1);
            return mp(edge[now].v,edge[now].val);
        }
    }f[2];
    inline int solve0(){
        f[1].Clear(),f[0].Clear();
        f[1].Hash(0,1),f[1].Hash(1,w[1]);
        for(res i=2;i<=n;i++){
            res d=i&1;
            RG Pair x;
            while((x=f[d^1].get()).fi!=-1){
                f[d].Hash((x.fi<<1)%(1<<k),x.se);
                if((x.fi&1)^1&&x.fi<(1<<(k-1)))f[d].Hash((x.fi<<1|1)%(1<<k),mul(x.se,w[i]));
            }
            f[d^1].Clear();
        }
        RG Pair x;
        res ans=0;
        while((x=f[n&1].get()).fi!=-1)add(ans,x.se);
        f[n&1].Clear();
        return Add(ans,kcz-1);
    }
    struct hash{
        struct E{
            int nxt;
            Pair v;
            int val;
            E() {}
            E(res nxt,RG Pair v,res val):nxt(nxt),v(v),val(val) {}
        }edge[300000+10];
        int head[HashMod],cnt,now,non;
        inline void ADD(const res &u,const RG pair<int,int> &v,const res &w){
            edge[++cnt]=E(head[u],v,w),head[u]=cnt;
        }
        inline void Clear(){
            memset(head,0,sizeof(head)),cnt=now=0,non=-1;
        }
        inline int &Query(const RG Pair &x){
            res s=(x.fi+x.se)%HashMod;
            for(res i=head[s];i;i=edge[i].nxt)if(edge[i].v==x)return edge[i].val;
            return non;
        }
        inline void Hash(const RG Pair &x,const res &k){
            res &o=Query(x);
            if(o==-1){
                res s=(x.fi+x.se)%HashMod;
                ADD(s,x,k);
            }
            else add(o,k);
        }
        inline pair<Pair,int> get(){
            now++;
            if(now>cnt)return mp(mp(-1,-1),-1);
            return mp(edge[now].v,edge[now].val);
        }
        inline void print(){
            for(res i=1;i<=cnt;i++)printf("%d %d %d\n",edge[now].v.fi,edge[now].v.se,edge[now].val);
        }
    }g[2];
    inline int solve1(){
        g[0].Clear(),g[1].Clear();
        for(res i=0;i<n;i++)w[i]=w[i+1];
        g[0].Hash(mp(0,0),1),g[0].Hash(mp(1,1),w[0]);
        for(res j=1;j<=(n-1)/k;j++){
            res d=j&1,t=j*k;
            RG pair<Pair,int> x;
            while((x=g[d^1].get()).se!=-1){
                res c=x.fi.fi>>(j-1)&1;
                g[d].Hash(x.fi,x.se);
                if(!c)g[d].Hash(mp(x.fi.fi|(1<<j),x.fi.fi|(1<<j)),mul(x.se,w[t]));
            }
            g[d^1].Clear();
        }
        res cur=((n-1)/k)&1;
        for(res i=1;i<k-1;i++){
            for(res j=0;j<=(n-1)/k;j++){
                res t=i+j*k;
                if(t>=n)break;
                cur^=1;
                RG pair<Pair,int> x;
                while((x=g[cur^1].get()).se!=-1){
                    res c=x.fi.fi>>j&1,d=0;
                    if(j!=0)d=x.fi.fi>>(j-1)&1;
                    if(c)g[cur].Hash(mp(x.fi.fi^(1<<j),x.fi.se),x.se);
                    else g[cur].Hash(x.fi,x.se);
                    if(!c&&!d)g[cur].Hash(mp(x.fi.fi|(1<<j),x.fi.se),mul(x.se,w[t]));
                }
                g[cur^1].Clear();
            }
        }
        //i=k-1
        for(res j=0;j<=(n-1)/k;j++){
            res t=k-1+j*k;
            cur^=1;
            RG pair<Pair,int> x;
            while((x=g[cur^1].get()).se!=-1){
                res c=x.fi.fi>>j&1,d=0,e=x.fi.se>>(j+1)&1;
                if(j!=0)d=x.fi.fi>>(j-1)&1;
                if(c)g[cur].Hash(mp(x.fi.fi^(1<<j),x.fi.se),x.se);
                else g[cur].Hash(x.fi,x.se);
                if(!c&&!d&&!e)g[cur].Hash(mp(x.fi.fi|(1<<j),x.fi.se),mul(x.se,w[t]));
            }
            g[cur^1].Clear();
            if(t+k>=n){
                res ans=0;
                while((x=g[cur].get()).se!=-1)add(ans,x.se);
                g[cur].Clear();
                return Add(ans,kcz-1);
            }
        }
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),k=read();
            for(res i=1;i<=n;i++)w[i]=read();
            if(k*k<=2*n)printf("%d\n",solve0());
            else printf("%d\n",solve1());
        }
    }
}